3152 取数游戏

有这样一个取数游戏，给出个正整数（2 <= n <= 100000），在其中选出个数，使得他们的gcd(最大公约数)最大，求这个最大的gcd。

输入

第一行一个整数n
第二行n个正整数

输出

一个一个数表示答案

数据范围

10% 2 <= n <= 10
30% 2 <= n <= 300
60% 2 <= n <= 5000
100% 2 <= n <= 100000

输入样例

输入样例1：
6
6 2 3 4 5 6
输入样例2：
5
5 5 6 10 15

输出样例

输出样例1：
3
输出样例2：
5

这里不给解析，直接放代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime> 
#define maxn 1000000
#define maxt 10
using namespace std;
typedef long long ll; 
int n;
ll  a[maxn+5];
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
int random(int l,int r){
    return (long long )rand()*rand()%(r-l+1)+l;
} 
int sz=0;
ll d[maxn+5];
int cnt[maxn+5];
void divide(ll x){
    sz=0;
    for(ll i=1;i*i<=x;i++){
        if(x%i==0){
            d[++sz]=i;
            if(x/i!=i) d[++sz]=x/i; 
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); 
    ll ans=0;
    for(int cas=1;cas<=maxt;cas++){
        ll x=a[random(1,n)];
        divide(x);
        sort(d+1,d+sz+1);
        for(int i=1;i<=sz;i++) cnt[i]=0;
        for(int i=1;i<=n;i++){
            int pos=lower_bound(d+1,d+1+sz,gcd(a[i],x))-d;
            cnt[pos]++;
        }
        for(int i=1;i<=sz;i++){
            for(int j=i+1;j<=sz;j++){
                if(d[j]%d[i]==0) cnt[i]+=cnt[j];
            }
        }
        for(int i=sz;i>=1;i--){
            if(cnt[i]*2>=n){
                ans=max(ans,d[i]);
                break;
            }
        }
    }
    printf("%I64d\n",ans);
    return 0;
}