ABC 125 C
题目描述(自己粗略描述一下)
现在有一堆数字,你可以再其中删掉一个,然后剩下的做 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;
}