E. Max Gcd
单点时限: 2.0 sec 内存限制: 512 MB
一个数组a，现在你需要删除某一项使得它们的gcd最大，求出这个最大值。
输入格式 第一行输入一个正整数n，表示数组的大小，接下来一行n个数，第i个数为ai。(2≤n≤105,1≤ai≤109)
输出格式 输出删除掉某个数以后的gcd的最大值。
样例
input 4 2 4 8 1 outpu| 2
input 4 1 2 3 4
output 1
提示 样例一：删除第四个元素后，2,4,8的最大公因子为2。 样例二：无论删除哪一个，最大公因子都为1。
这个题刚开始想着直接暴力，后来发现时间不允许就放弃了，赛后我是师父说直接先把数组从前到后依次gcd存在一个数组里，然后在从后向前依次gcd再放另一个数组里，然后在直接暴力就行了！
红线代表从前向后依次gcd，蓝线是从后向前。然后一个一个去除保留最大的数据就行！
代码语言：javascript复制#include<algorithm>
#include<iostream>
using namespace std;
int a[100100],b[100100],c[100100];
int main()
{
int n;
cin>>n;
cin>>a[1];
b[1]=a[1];
for(int i=2;i<=n;i )
{
cin>>a[i];
b[i]=__gcd(b[i-1],a[i]);//从前向后依次gcd
}
c[n]=a[n];
for(int i=n-1;i>=1;i--)
{
c[i]=__gcd(c[i 1],a[i]);//从后向前依次gcd
}
int maxn=max(b[n-1],c[2]);//因为防止数组下标越界所以事先比较去掉第一项和
//去掉最后一项哪个大，保留打的一个
for(int i=2;i<n;i )
{
//b[i-1]和c[i 1]刚好是第i项之前的所有项的gcd和第i项之后的所有项的gcd
maxn=max(__gcd(b[i-1],c[i 1]),maxn);
//因为一直保留的是最大的值，所以最后的maxn就是答案
}
cout<<maxn<<endl;
}
