Coprime Sequence（前后缀GCD）

Description

Do you know what is called ``Coprime Sequence''? That is a sequence consists of $n$ positive integers, and the GCD (Greatest Common Divisor) of them is equal to 1. 
``Coprime Sequence'' is easy to find because of its restriction. But we can try to maximize the GCD of these integers by removing exactly one integer. Now given a sequence, please maximize the GCD of its elements.

 

Input

The first line of the input contains an integer $T(1leq Tleq10)$, denoting the number of test cases. 
In each test case, there is an integer $n(3leq nleq 100000)$ in the first line, denoting the number of integers in the sequence. 
Then the following line consists of $n$ integers $a_1,a_2,...,a_n(1leq a_ileq 10^9)$, denoting the elements in the sequence.

 

Output

For each test case, print a single line containing a single integer, denoting the maximum GCD.

 

Sample Input

3

3

1 1 1

5

2 2 2 3 2

4

1 2 4 8

 

Sample Output

1

2

2

 

 

 

 

 

题目意思：给出n个数，去掉其中的一个数，得到一组数，使其最大公约数最大。第一组样例，去掉一个1，得到最大的最大公约数是1。第二组样例，去掉3，得到最大的最大公约数为2。第三组样例，去掉1，得到的最大的最大公约数是2。

 

解题思路：这里使用了之前我没有用到过的一种方法。依次遍历每个数，算出这个数左边的一堆数的最大公约数x1，再算出这个数右边的一堆数的最大公约数x2，gcd(x1,x2)即为删去当前数后剩下的数的最大公约数。遍历每个数得到的最大gcd即为所求。而每个数左边的gcd和右边的gcd可以用O(n)的时间复杂度预处理，遍历每个数是跟前面并列的O(n)复杂度，故可线性解决。

 

#include<stdio.h>
#include<algorithm>
using namespace std;
int gcd(int a,int b) ///基础 辗转
{
    int r;
    while(b>0)
    {
         r=a%b;
         a=b;
         b=r;
    }
    return a;
}
int a[100005],b[100005],c[100005];
int main()
{
    int t,n,i,ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        b[0]=a[0];
        c[n-1]=a[n-1];
        for(i=1;i<n;i++)///求前缀GCD
        {
            b[i]=gcd(b[i-1],a[i]);
        }
        for(i=n-2;i>=0;i--)///求后缀GCD
        {
            c[i]=gcd(c[i+1],a[i]);
        }
        ans=max(c[1],b[n-2]);
        for(i=1;i<n-1;i++)
        {
            ans=max(ans,gcd(b[i-1],c[i+1]));
        }
        printf("%d
",ans);

    }
    return 0;
}