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

现在有一堆数字，你可以再其中删掉一个，然后剩下的做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;
} 

本文链接：https://kaispace.com.cn/index.php/archives/364/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者