这道题是给N个数。。都小于10^6次方，求出其中两两之间最大的最大公约数是多少。。
很显然可以暴力求。。不过那是N^2的。。注意到所有数都在10^6次方一下。。所以
可以吗枚举答案来检测。。就是说开一个数组，大小为10^6。。每个中记录其中在这个索引的数有多少个。。。那么可以很方便的检测出一个数的倍数有多少个。。只要>1就更新答案。。。
计算复杂度是10^6*log(10^6)的。。。
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000000;
class solve
{
short Num[maxn+1];int M;
void init()
{
int n,x;scanf("%d",&n);memset(Num,0,sizeof(Num));M=0;
while(n–) scanf("%d",&x),Num[x]++,M=max(M,x);
}
bool check(int x)
{
int cnt=0;
for(int i=x;i<=M&&cnt<2;i+=x)
cnt+=Num[i];
return cnt>1;
}
int work()
{
for(int i=M;i;i–) if(check(i)) return printf("%dn",i);
}
public:
solve()
{
init();
work();
}
};
int main()
{
solve now;
}顺便发一下Gedit的图片。。代码漂亮死了。。享受啊。。