zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
int ans[300000],bns[300000],ap[1000005];
using namespace std;
int main() {
    int n;
    scanf("%d",&n);
    int i,j;
    int maxx = 0;
    for(i = 0; i < n; i++)
        scanf("%d",&ans[i]),
        maxx = max(ans[i],maxx);

    sort(ans,ans+n);
    int cn = 0;
    bns[cn++] = ans[0];
    int t =bns[0];
    for(i = 1; i < n; i++)
        if(ans[i]!=t) {
            t = ans[i];
            bns[cn++] = t;
        }

    if(n == 1)
        printf("0\n");
    else {
        int ask = 0;
        for(i = cn-1; i >= 0; i--) {
            if(bns[i]!=1) {
                for(j = 2; bns[i]*j <= maxx+bns[i]; j++) {
                    int l = i+1,r = cn-1;
                    int id = -1;
                    while(l <= r) {
                        int mid = (l+r)/2;
                        if(bns[mid] < bns[i]*j) {
                            id = mid;
                            l = mid + 1;
                        } else r = mid-1;
                    }
                    if(id!=-1) 
                        ask = max(bns[id]%bns[i],ask);
                }
            }
            if(ask >= bns[i])break;
        }
        printf("%d\n",ask);
    }
}
51nod 1421 最大MOD值
comment评论
Search
search