Codeforces Round ＃276 (Div. 1) B. Maximum Value

Codeforces Round #276 (Div. 1) B. Maximum Value

题意： 给定一个长为 $n$ 的序列 $\{a_i\}$ ，求序列中最大的 $a[i]$$mod$$a[j]$ 其中 $a_i>a_j$

思路： 考虑到 $a_i$ 的取值最大为 $10^6$ ，我们可以暴力枚举 $a_i$ 的倍数，枚举值不超过 $2\ast 10^6$ 即可，看似 $O(n^2)$ 的复杂度，实则符合调和级数的性质，即 $N$$\ast$$1$$+$$N$$\ast$$\frac{1}{2}$$+$$N$$\ast$$\frac{1}{3}$$...$$=$$NlogN$ ，然后再通过前缀和操作，$O(n)$ 预处理出来每个数离当前数倍数最近的数，从而不断更新最大的模数。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2E6+10;
bool vis[N];
int pre[N];
int n;
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
    
        int x;
        cin>>x;
        vis[x]=true;
    }
    for(int i=1;i<N;i++){
    
        if(vis[i])pre[i]=i;
        else pre[i]=pre[i-1];
    }
    int ans=0;
    for(int i=2;i<N;i++){
    //调和级数
        if(vis[i]){
    
            for(int j=2*i;j<N;j+=i){
    
                ans=max(ans,pre[j-1]%i);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}