codeforces D. Maximum Value

约定不等于承诺〃 2022-07-24 09:16 183阅读 0赞

D. Maximum Value

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a sequence *a* consisting of *n* integers. Find the maximum possible value of ![78b367327f7d7a7eba50f5e1ebfaf0cb199e1837.png][] (integer remainder of *a**i* divided by*a**j*), where 1 ≤ *i*, *j* ≤ *n* and *a**i* ≥ *a**j*.

Input

The first line contains integer *n* — the length of the sequence (1 ≤ *n* ≤ 2·105).

The second line contains *n* space-separated integers *a**i* (1 ≤ *a**i* ≤ 106).

Output

Print the answer to the problem.

Examples

input

3
    3 4 5

output

题意: 给你n个数, 求最大的ai%aj的值.

分析:  可以将原先数组排个序, 然后去重, 用类似于埃氏筛选的方法对于每个数a\[i\]枚举它的倍数, 然后对于每个倍数x, 找小于x的最大的a\[k\]; 那么a\[i\]-(x-a\[k\])就是a\[k\]模a\[i\]的值, (x-a\[k\])是最小的, 因此a\[i\]-(x-a\[k\])就是最大的, 不断更新答案就行啦.

开始是用二分找小于x的最大的值, 后来发现可以用一个数组来做;

#include<bits/stdc++.h>
    
    #define inf 0x3f3f3f3f
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    const int N=2000010,MOD=1e9+7;
    int a[200020];
    int pre[N];
    bool have[N];
    
    int main()
    {
        int n;cin>>n;
        for(int i=0;i<n;i++) scanf("%d",a+i),have[a[i]]=1;
        sort(a,a+n);
        n = unique(a,a+n)-a;
        int mx = a[n-1];
        mx<<=1;
        int last=0;
        for(int i=1;i<=mx;i++){
            if(!have[i]) pre[i] = last;
            else{
                pre[i]=last;
                last=i;
            }
        }
    
        int ans=0;
        int i=a[0]==1;
        for(;i<n;i++){
            for(int j=a[i]+a[i];j<mx;j+=a[i]){
                if(j-a[n-1]>=a[i]) break;
                int ret = pre[j];
                if(j-ret >= a[i]) continue;
                ans = max(ans,a[i]-(j-ret));
            }
        }
        cout<<ans<<endl;
        return 0;
    }

[78b367327f7d7a7eba50f5e1ebfaf0cb199e1837.png]: /images/20220722/95644cc8209e4293beb92ad08d7d71d7.png