单点时限: 2.0 sec

内存限制: 512 MB

一个数组a，现在你需要删除某一项使得它们的gcd最大，求出这个最大值。

样例

4

2 4 8 1

2

4

1 2 3 4

1

#include<iostream>

#include<algorithm>

#define N 100010

using namespace std;

typedef long long ll;

ll arr[N];

ll pre[N]={},od[N]={};//前缀与后缀

int main(){

    int n;

    cin>>n;

    for(int i=;i<=n;i++){

        cin>>arr[i];

    }

    pre[]=arr[];

    od[n]=arr[n];

    for(int i=;i<=n;i++){

        pre[i]=__gcd(pre[i-],arr[i]);//前缀gcd

    }

    for(int i=n-;i>;i--){

        od[i]=__gcd(od[i+],arr[i]);//后缀gcd

    }

    ll max1=;

    ll p;

    for(int i=;i<=n;i++){

        if(i==){

            p=od[i+];

        }

        else {

            p=__gcd(pre[i-],od[i+]);//pre[i-1]指的是前i-1个个数的gcd,od[i+1]指的是从i+1到第N个数的gcd

            if(p>max1){

            max1=p;

            }

        }

    }

    cout<<max1<<endl;

    return ;

}