Sgu/499

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
Greatest Greatest Common Divisor	★★☆☆☆	答案正确	100	2015-2-21 16:21:27	无

（AC 680）

题意

给出n个数{}中两两之间最大公约数之中最大的一个。

题解

• 从max{}到1枚举每个数k，分别判断是否存在和使得，（为整数）。
• 由于题目限定了的范围，只需要枚举m，判断是否有两个m*k是否属于{}即可（可以用数组统计出现次数）。
• 容易知道复杂度为。

代码

499.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; #define si(n) scanf("%d",&n) #define dsi(n) int n;si(n) #define f(i,n) for(int i=1;i<=n;++i) #define fi(i,p,n) for(int i=p;i<=n;++i) #define fd(i,n) for(int i=n;i!=0;--i) #define fdi(i,p,n) for(int i=n;i>=p;--i) int countA[1000010]={},maxA=0; int main() { dsi(n); f(i,n) { dsi(a); ++countA[a]; maxA=max(maxA,a); } fd(i,maxA) for(int j=1,o=0;i*j<=maxA;++j) { o+=countA[i*j]; if(o>=2) { cout<<i<<endl; return 0; } } }

参考资料和拓展阅读

• http://blog.csdn.net/duanxian0621/article/details/7737763