传送门
根据国家集训队2014论文集中胡泽聪的随机化算法可以通过这道题。
对于每个数，它有12" role="presentation" style="position: relative;">1212的概率在最后的答案序列中，这样我们每次随机出序列中的一个数，然后看它的因子有没有符合条件的更新答案就行了。
代码；
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int n,tot[N],sum[N];
ll x[N],ans,g[N],divv[N];
set<ll>s;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline ll gcd(ll a,ll b){while(b){ll t=a;a=b,b=t%a;}return a;}
inline ll max(ll a,ll b){return a>b?a:b;}
inline void calc(int pos){
int siz=0;
for(int i=1;i<=n;++i)g[i]=gcd(x[i],x[pos]);
for(int i=1;1ll*i*i<=x[pos];++i){
if(x[pos]%i)continue;
divv[++siz]=i;
if(1ll*i*i==x[pos])continue;
divv[++siz]=x[pos]/i;
}
sort(divv+1,divv+siz+1),siz=unique(divv+1,divv+siz+1)-divv-1;
for(int i=1;i<=siz;++i)tot[i]=sum[i]=0;
for(int i=1;i<=n;++i)++tot[lower_bound(divv+1,divv+siz+1,g[i])-divv];
for(int i=1;i<=siz;++i){
if(divv[i]<=ans)continue;
for(int j=i;j<=siz;++j)if(divv[j]%divv[i]==0)sum[i]+=tot[j];
}
for(int i=siz;i;--i){
if(divv[i]<=ans)break;
if(sum[i]*2>=n){ans=divv[i];break;}
}
}
int main(){
srand(time(NULL)),n=read(),ans=1;
for(int i=1;i<=n;++i)x[i]=read();
for(int i=1,dep=0;dep<=12&&i<=(n<<1);++dep,++i){
int pos=1ll*rand()*rand()%n+1;
if(s.count(x[pos])){--dep;continue;}
s.insert(x[pos]),calc(pos);
}
printf("%I64d",ans);
return 0;
}