南阳理工学院ACM多乐赛暨16级退役纪念赛　F 序列操作Ⅱ

题目来源：http://acm.nyist.edu.cn/problem/1666

题目描述:

给定长度为N的正整数序列 , 从中选择一个数删除，使剩下数字的最大公约数最大。
求删除后的最大公约数。

输入描述:

第一行是一个数字，表示 N。
第二行是 N 个数。
1 <= N <= 10^6, 1 <= A_i <= 10^9.

输出描述:

一个数字，表示输出删除后的最大公约数。

样例输入:

5
21 13 9 15 12

样例输出:

3

前后缀跑gcd（最后比较的时候选取前缀第n-1个和后缀第2个中最大的

参考代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
const int N=1e6+5;
#define inf 0x3f3f3f3f
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
ll a[N],b[N],c[N];
int main()
{
    ll n;
    //freopen("//home/nuoyanli//文档//0615//F//data//secret//5.in", "rep", stdin);
    //freopen("output.out", "w", stdout);
    scanf("%lld",&n);
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    if(n==1)
        printf("%lld\n",a[1]);
    else
    {
        b[1]=a[1];
        for(int i=2; i<=n; i++)
            b[i]=gcd(b[i-1],a[i]);
        c[n]=a[n];
        for(int i=n-1; i>=1; i--)
            c[i]=gcd(c[i+1],a[i]);
        ll ans=max(c[2],b[n-1]);
        for(int i=2; i<=n-1; i++)
            ans=max(ans,gcd(b[i-1],c[i+1]));
        printf("%lld\n",ans);
    }
    return 0;
}