gcd

题目描述

Alice和Bob在玩数字游戏： 
Alice随机给出n个整数a1、a2、……、an，要求Bob从这些数字中选择一个ai，用[1, 109]之间的任意整数进行替换（替换的数字可能和ai相同），希望替换后n个数的最大公约数尽可能大。 

输入

输入第一行为一个数字n 
第二行包括n个用空格隔开的整数，表示Alice给出的n个数 

输出

输出一个数，表示替换后n个数的最大公约数

样例输入

3
7 6 8

样例输出

2

提示

对于30%的数据，1<=n<=1000 

对于100%的数据，2<=n<=106，1<ai<=109 

首先你会发现暴力过不了，用欧几里得去查找公约数是O（n²）的，用前缀和是O（n log（n））的可以过，BUT我不会打...所以我用了一种玄学的方法，排个序然后去瞎搞判断一个数有几个约数，如果约数个数>=2就不找了：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100001];
int ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=a[2];i>=2;i--){
        int ji_lu=0;
        for(int j=1;j<=n;j++){
            if(a[j]%i!=0) ji_lu++;
            if(ji_lu>=2) break;
        }
        if(ji_lu<=1){
            ans=i;
            break;
        }
    }
    cout<<ans;
}