题目描述（自己粗略描述一下）

现在有一堆数字，你可以再其中删掉一个，然后剩下的做 GCD。

数据范围

$ 2≤数字数量≤10^5 $

解题思路

看到数量就知道暴力过不了，那么肯定要优化咯。我最开始想的是用二分思想优化，但是由于太蒟蒻 1 小时 25 分钟没写出来。

之后我的老师告诉我是用一种前缀和后缀的思想做。（不是前缀和）先预处理一下所有去掉的数字之前的数字的 gcd 和之后的 gcd。然后每一个的答案就是 gcd(前面的 gcd, 后面的 gcd)。

GCD 的题目再比赛中经常出现，所以代码要背熟。

int gcd(int a,int b){
    if(a%b==0){
        return b;
    }
    return gcd(b,a%b);
}

代码

#include<iostream>
using namespace std;
int a[100005];
int ans[100005];
int qian[100005];
int hou[100005];
int gcd(int v,int b){
    if(v%b==0){
        return b;
    }
    return gcd(b,v%b);
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    qian[0]=a[2];
    qian[1]=a[1];
    hou[0]=a[n-1];
    hou[1]=a[n];
    for(int i=1;i<n;i++){
        hou[i+1]=gcd(hou[i],a[n-i]);
    }
    for(int i=1;i<n;i++){
        qian[i+1]=gcd(qian[i],a[i+1]);
    }
    for(int i=1;i<=n;i++){
        ans[i]=gcd(qian[i-1],hou[n-i]);
    }
    int maxn=0;
    for(int i=1;i<=n;i++){
        maxn=max(ans[i],maxn);
    }
    cout<<maxn;
    return 0;
}