题目大意：给你n个数，从里面选2个，使得它们的最大公约数最大，输出这个最大公约数
原本前一天在想一个相似的题目，但是是选k个，所以数据范围变小了，还是能用选k个的想法做。
思路很简单，首先由于这n个数不超过1e5，所以可以开个桶来存出现次数。
然后再从其中最大的数倒序枚举每一个自然数，再枚举自然数的倍数，如果这个自然数的倍数在桶里面出现不少于2次，这个自然数就是答案。
代码用了fread快读，所以目前在hdu这份代码是rank1 (78ms中提交时间最早的那一个)
代码
|
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 44 45 46 |
#include<bits/stdc++.h> using namespace std; int maxa; int a[100005]; int n,k; inline char nc(){ static char buf[100005],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100005,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int num=0;char ch='a';int f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=nc();} while(isdigit(ch)){num=(num<<3)+(num<<1)+(ch^48);ch=nc();} return f*num; } int main(){ int t=read(); int T=t; while(t--){ memset(a,0,sizeof(a));maxa=0; printf("Case #%d: ",T-t); n=read();k=2;//这里让k=2，如果是选k个的话，就输入k就行了 for(int i=1;i<=n;i++){ int tmp=read(); maxa=max(maxa,tmp); a[tmp]++; } for(int i=maxa;i>=1;i--){ int cnt=0,flag=0; for(int j=i;j<=maxa;j+=i){ cnt+=a[j]; if(cnt>=k){ flag=1; printf("%d\n",i); break;//由于是倒序枚举，找到的答案肯定是最优的 } } if(flag)break; } } return 0; } |
%%%%