HDU 5207 Greatest Greatest Common Divisor

题目链接：

hdu:http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=153598

bc(中文):http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=577&pid=1002

题解：

1、对于每个输入，枚举它的因子，并统计，结果存在mmp数组中，最后再倒过来扫一遍mmp数组，其中第一个mmp[i]>=2的，就是答案。

　　时间复杂度：O(n*sqrt(n) )

这个跑了1404ms

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn=1e5+;

 typedef long long LL;

 int n;

 int mmp[maxn];

 void init(){

     memset(mmp,,sizeof(mmp));

 }

 int main() {

     int tc,kase=;

     scanf("%d",&tc);

     while(tc--) {

         scanf("%d",&n);

         init();

         for(int i=;i<n;i++){

             int x;

             scanf("%d",&x);

             for(int div=;div*div<=x;div++){

                 if(x%div==){

                     mmp[div]++;

                     if(x/div!=div) mmp[x/div]++;

                 }

             }

         }

         int ans=;

         for(int i=maxn-;i>=;i--){

             if(mmp[i]>=){

                 ans=i; break;

             }

         }

         printf("Case #%d: %d\n",++kase,ans);

     }

     return ;

 }

2、用筛法预处理出10^5以内所有数的因子，然后采用同上的方法做。

筛法的时间复杂度：O(n+n/2+n/3+n/4+...n/n)=O(n*(1+1/2+1/3+...1/n))=O(n*logn)

(附：欧拉公式：1+1/2+1/3+……+1/n=ln(n)+C)

这个跑了374ms

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 using namespace std;

 const int maxn=1e5+;

 typedef long long LL;

 int n;

 int mmp[maxn];

 vector<int> Div[maxn];

 void pre_for_div(){

     for(int i=;i<maxn;i++){

         for(int t=i;t<maxn;t+=i){

             Div[t].push_back(i);

         }

     }

 }

 void init(){

     memset(mmp,,sizeof(mmp));

 }

 int main() {

     pre_for_div();

     int tc,kase=;

     scanf("%d",&tc);

     while(tc--) {

         scanf("%d",&n);

         init();

         for(int i=;i<n;i++){

             int x;

             scanf("%d",&x);

             for(int j=;j<Div[x].size();j++){

                 mmp[Div[x][j]]++;

             }

         }

         int ans=;

         for(int i=maxn-;i>=;i--){

             if(mmp[i]>=){

                 ans=i; break;

             }

         }

         printf("Case #%d: %d\n",++kase,ans);

     }

     return ;

 }

3、先统计每个输入的值出现的个数，存在cnt里面；然后从大到小枚举答案ans=d，求解sum(cnt[d],cnt[d*2],cnt[d*3]...)，如果sum>=2说明答案就是d。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 using namespace std;

 const int maxn=1e5+;

 typedef long long LL;

 int n;

 int cnt[maxn];

 void init(){

     memset(cnt,,sizeof(cnt));

 }

 int main() {

     int tc,kase=;

     scanf("%d",&tc);

     while(tc--) {

         scanf("%d",&n);

         init();

         for(int i=;i<n;i++){

             int x;

             scanf("%d",&x);

             cnt[x]++;

         }

         int ans=;

         for(int g=maxn-;g>=;g--){

             int tmp=;

             for(int sum=g;sum<maxn;sum+=g){

                 tmp+=cnt[sum];

             }

             if(tmp>=){

                 ans=g; break;

             }

         }

         printf("Case #%d: %d\n",++kase,ans);

     }

     return ;

 }