Alice和Bob在玩数字游戏：
Alice随机给出n个整数a1、a2、……、an，要求Bob从这些数字中选择一个ai，用[1, 109]之间的任意整数进行替换（替换的数字可能和ai相同），希望替换后n个数的最大公约数尽可能大。
正常来讲，我们会想到一个图像
一个下降的图像代表GCD，然后会根据让GCD下降的位置来判断改变一个相应的数。
但是我们会发现，让GCD下降的数会有多个，而我们无法确定改变哪一可以让GCD最大，因为这些书之间也会有GCD
所以我们抛开这个图像，从最暴力的角度进行考虑，我们发现可以美剧去掉的数，算出其他的数的GCD，选出其中最大的就是结果
直接暴力的话是n^2logn的，我们来看如何让每次去掉一个数时用更快的方法求出其他数的GCD，我们考虑维护类似于前缀和的东西，然后将选中的数的前面的和后面的跑一次GCD即可。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<string> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; return x*f; } inline int gcd(int x,int y){ if(!y) return x; return gcd(y,x%y); } int n; int a[1000006],s1[1000006],s2[1000006]; int main(){ n=rd(); for(int i=1;i<=n;i++) a[i]=rd(); s1[1]=a[1]; s2[n]=a[n]; for(int i=2;i<=n;i++) s1[i]=gcd(s1[i-1],a[i]); for(int i=n-1;i>=1;i--) s2[i]=gcd(s2[i+1],a[i]); int ans=max(s1[n-1],s2[2]); for(int i=2;i<n;i++) ans=max(ans,gcd(s1[i-1],s2[i+1])); printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/WWHHTT/p/10907399.html