20分做法

直接用 $O(n^2)$ 的复杂度来做，暴力枚举最大的 $gcd(a_i,a_j)$

#include<bits/stdc++.h>
using namespace std;
long long a[1000006];
long long gcd(long long a,long long b){
	return b?gcd(b,a%b):a;
}
int main(){
	//freopen("maxgcd.in","r",stdin);
	//freopen("maxgcd.out","w",stdout);
	long long n,gcdd,maxx=-1;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			maxx=max(maxx,gcd(a[i],a[j]));
	cout<<maxx;
}

60分做法

注意到，任意一个最大 gcd 都一定是两个数列中不同数的因数，故我们可以用一个桶存储每个因数的出现次数，然后找到最大的出现次数 $\ge 2$ 的因数，时间复杂度 $O(n \sqrt n)$

#include<bits/stdc++.h>
using namespace std;
int a[1000006],tong[1000006];
int main(){
	//freopen("maxgcd.in","r",stdin);
	//freopen("maxgcd.out","w",stdout);
	int n,maxx;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j*j<=a[i];j++){
			if(a[i]%j==0){
				tong[j]++;
				if(j*j!=a[i]) tong[a[i]/j]++;
			}
		}
	}
	for(int i=1;i<=1000000;i++) if(tong[i]>=2) maxx=i;
	cout<<maxx;
}

100分做法

我们换一个角度思考，用时间复杂度 $O(n log n)$ 的倍数遍历。将原数列的数存进桶里，计算每一个因数是否能倍数对应出两个及以上的原数列数。

#include<bits/stdc++.h>
using namespace std;
long long a[1000006],tong[1000006];
int main(){
   //freopen("maxgcd.in","r",stdin);
   //freopen("maxgcd.out","w",stdout);
   int n,cnt=0,ans;
   cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i];
   for(int i=1;i<=n;i++) tong[a[i]]++;
   for(int i=1;i<=1000000;i++){
      cnt=0;
      for(int j=i;j<=1000000;j+=i) cnt+=tong[j];
      if(cnt>=2) ans=i;
   }
   cout<<ans;
   return 0;
}