hdoj 6025 Coprime Sequence

互质数列，到手疯狂模拟。暴力选手哭泣
后来粗略看了网解，第一次了解前后缀这么神奇的东西！！
自己做tle三次，果然...只是理解了“缀”的字面意思。
//前缀这个“缀”字的作用，就是要利用前面已经算过的值；
//而不是每来一次，就线性遍历一次！

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6025

解题思路：
模拟是不会有好结果的，前后缀了解一下？
对于num数组里的每一个元素，left记录这个元素前边所有元素的gcd,right数组记录这个元素后面所有元素的gcd，那么这俩取gcd,是不是就是删去本元素后序列的gcd值呢？
注意到gcd的left和right要（和本身取gcd从而）递归取，否则会超时的。。

AC代码：

//前缀这个“缀”字的作用，就是要利用前面已经算过的值；
//而不是每来一次，就线性遍历一次！ 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int num[n],left[n],right[n],max=-1;
        
        memset(left,0,4*n);         //left的含义是包含本元素在内的前缀gcd 
        memset(right,0,4*n);        //right的含义是包含本元素在内的后缀gcd 
         
        for(int i=0;i<n;i++)
            cin>>num[i];
        
        left[0]=num[0];                //缀的初始化 
        right[n-1]=num[n-1]; 
        
        //求前缀和
        for(int i=1;i<n;i++)
        {
            left[i]=__gcd(left[i-1],num[i]);
        }    
        
        //求后缀和
        for(int i=n-2;i>=0;i--)
        {
            right[i]=__gcd(right[i+1],num[i]);
        }        
        
        for(int i=0;i<n;i++)
        {
            if(i==0)                    //首元素所需求项，等于！不包含自身！的后缀gcd 
                num[i]=right[i+1];
            else if(i==n-1)                //同理 ,尾元素处理 
                num[i]=left[i-1];    
            else 
                  num[i]=__gcd(right[i+1],left[i-1]);
            
            if(num[i]>max)
                max=num[i]; 
        } 
        
        printf("%d\n",max);
    }
    
    
    return 0;
}