题目链接：
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 ;
}