Coprime Sequence （HDU 6025）前缀和与后缀和的应用

题意：给出一串数列，这串数列的gcd为1，要求取出一个数使取出后的数列gcd最大。

题解：可以通过对数列进行预处理，求出从下标为1开始的数对于前面的数的gcd（数组从下标0开始），称为前缀gcd，再以类似的方式求出后缀gcd，然后从第一个数开始枚举取出后的gcd（这个数的前缀gcd与后缀gcd的gcd）。找出最大的gcd数即可。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[],pre[],suf[];

int gcd(int a,int b)

{

    return b==?a:gcd(b,a%b);

}

int main(){

    int t,n;

    while(~scanf("%d",&t)){

        while(t--){

            scanf("%d",&n);

            for(int i=;i<n;i++){

                scanf("%d",&a[i]);

            }

            pre[]=a[];

            for(int i=;i<n;i++){

                    pre[i]=gcd(pre[i-],a[i]);

            }

            suf[n-]=a[n-];

            for(int i=n-; i>=; i--){

                    suf[i]=gcd(suf[i+],a[i]);

            }

            int ans=max(suf[],pre[n-]);

            for(int i=;i<n-;i++){

                    ans=max(ans,gcd(pre[i-],suf[i+]));

            }

            printf("%d\n",ans);

        }

    }

    return ;

}