O(n2)tle。O(nlognlogn)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
const int nmax=2e5+5;
int a[nmax];
int main(){
int n=read();
rep(i,1,n) a[i]=read();
sort(a+1,a+n+1);
int ans=0,tp;
rep(i,1,n-1){
for(int j=a[i]+a[i];j<=a[n]*2;j+=a[i]){
tp=lower_bound(a+1,a+n+1,j)-a-1;ans=max(ans,a[tp]%a[i]);
}
}
printf("%d\n",ans);
return 0;
}
收藏
关注有一个a数组，里面有n个整数。现在要从中找到两个数字(可以是同一个) ai,aj ，使得 ai mod aj 最大并且 ai ≥ aj。
Input
单组测试数据。
第一行包含一个整数n，表示数组a的大小。(1 ≤ n ≤ 2*10^5)
第二行有n个用空格分开的整数ai (1 ≤ ai ≤ 10^6)。
Output
输出一个整数代表最大的mod值。
Input示例
3
3 4 5
Output示例
2