Coprime Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3065    Accepted Submission(s): 1424

 

Problem 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(1≤T≤10), denoting the number of test cases.
In each test case, there is an integer n(3≤n≤100000) in the first line, denoting the number of integers in the sequence.
Then the following line consists of n integers a1,a2,...,an(1≤ai≤109), 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

 

题意：求几个数中删去一个数后能得到的最大GCD是多少。

因为是删去一个数后求得GCD，所以求出每个数前面元素的GCD和后面元素的GCD，在对着两个值求一遍GCD就能得到删去这个数后的GCD了，取出最大值即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
#define maxn 100005

int gcd1[maxn],gcd2[maxn];
int a[maxn];

int main()
{
	int t,n,i;
	cin>>t;
	while(t--)
	{
		cin>>n;
		gcd1[0]=gcd2[n+1]=0;
		for(i=1;i<=n;i++)
		{
			cin>>a[i];
			if(i==1)
				gcd1[i]=a[i];
			else
				gcd1[i]=__gcd(gcd1[i-1],a[i]);
		}
		for(i=n;i>=1;i--)
		{
			if(i==n)
				gcd2[i]=a[n];
			else
				gcd2[i]=__gcd(gcd2[i+1],a[i]);
		}
		int minn=-inf;
		for(i=1;i<=n;i++)
		{
			minn=max(minn,__gcd(gcd1[i-1],gcd2[i+1]));
		}
		cout<<minn<<endl;
	}
	return 0;
}