CF484B

DDF_ · 2025-07-30 14:35:30 · 题解

题面

一个数组，求数组中大数模小数的最大值。

题解

你好。重复的元素没有用，而且由于只需要满足 a_{i} \ge a_{j}，所以可以直接排序并去重。

第一个暴力就是直接从小到大排序并去重，然后枚举 i \in [1,n],j \in [1,i)，时间复杂度 O(n^{2})。

然后发现这里的 a_{i} 有一些特殊的数据性质，它只开到了 10^{6}，于是可以打出第二个暴力。

排序去重后，枚举 a_{i}，并从大到小枚举它的模数 j 判断 j 是不是可行的解，我开了个桶存 s_{i} 表示 i 在不在数组 a 中，然后由 x=j+a_{i} 往上跳，如果遇到 s_{x}=1，则此时 j 唯一个合法的解。

然后发现不管怎么剪枝复杂度还是过不了，那考虑再次优化算法。

把枚举 j 优化，对于每个 a_{i}，由 x=2 \times a_{i} 向上跳。找在 [x-a_{i},x) 中离 x 最近的数字。

还记得 a_{i} \le 10^{6} 吗？开一个数组 s， s_{x} 存最大的 a_{i} 使得 a_{i} \le x（[1,x] 中离 x 最近的数）。所以对于每个 a_{i} 有 s_{a_{i}}=a_{i}，接着做一下前缀处理就行了。

最后只需要求 s_{x-1}，并且判断一下它是否在区间 [x-a_{i},x) 中即可。

令 m 为 a_{i} 的最大值，排序去重后往上跳的时间开销为 T(\sum_{i=1}^{n} \frac {m}{a_{i}})，不超过调和级数 O(m \log m)。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+15;
int n;
int a[N],s[N*10],m;
int ans;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),m=max(a[i],m);
    sort(a+1,a+1+n);
    n=unique(a+1,a+1+n)-a-1;
    for(int i=1;i<=n;i++) s[a[i]]=a[i];
    for(int i=1;i<=2*m;i++) if(!s[i]) s[i]=s[i-1];
    for(int i=1;i<n;i++) {
        for(int j=2*a[i];j<=m+a[i];j+=a[i]) {
            if(s[j-1]>j-a[i]) ans=max(ans,s[j-1]%a[i]);
        }
    }
    printf("%d",ans);
    return 0;
}