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$ 的倍数,The enumeration value does not exceed $2\ast 10^6$ 即可,看似 $O(n^2)$ 的复杂度,In fact, it conforms to the properties of harmonic series,即 $N$$\ast$$1$$+$$N$$\ast$$\frac{1}{2}$$+$$N$$\ast$$\frac{1}{3}$$...$$=$$NlogN$ ,And then through the prefix and operation,$O(n)$ Preprocess each number to the nearest multiple of the current number,Thus continuously updating the largest modulus.

代码：

#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;
}