Problem
有一个a数组,里面有n个整数。现在要从中找到两个数字(可以是同一个) ai,aj ,使得 ai mod aj 最大并且 ai ≥ aj。
Solution
遍历模数,枚举倍数,对于每一个倍数,找到比倍数小的最大值。这个最大值之前预处理出来,注意细节。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include<stdio.h> #include<iostream> #include<cstring> #include<algorithm> #include<map> #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; #define db double #define ll long long inline int rd(){ int x=0; char ch=0; while(ch<'0'||ch>'9') {ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,a[200020],mx,ans; int f[1000020]; int main(){ n=rd(); for(int i=1;i<=n;i++){ a[i]=rd(); mx=max(mx,a[i]); } sort(a+1,a+1+n); n=unique(a+1,a+1+n)-(a+1); a[n+1]=1000000; for(int i=1;i<=n;i++){ for(int j=a[i]+1;j<=a[i+1];j++){ f[j]=a[i]; } } for(int i=1;i<=n;i++){ for(int k=2;;k++){ int sum=k*a[i]>1000000?mx:f[k*a[i]]; ans=max(ans,sum%a[i]); if(k*a[i]>1000000) break; } } printf("%d\n",ans); return 0; }
|