ZCMU Problem E: Subarray GCD(n个数的最大公约数)

时间:2022-06-25 05:18:34

Problem E: Subarray GCD

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 44  Solved: 27
[Submit][Status][Web Board]

Description

Given an array A1,A2...AN, you have to print the size of the largest contiguous subarray such that
GCD of all integers in that subarray is 1.

Formally,
For a subarray Ai,Ai+1...Aj where 1 ≤ i < j ≤ N to be valid: GCD(Ai,Ai+1...Aj) should be 1. You have to print the size of the largest valid subarray.

If no valid subarray exists, output -1.

Note:A single element is not considered as a subarray according to the definition of this problem.

 

 

Input

First line contains T, the number of testcases. Each testcase consists of N in one line followed by Nintegers in the next line.

Constraints

 

  • 1 ≤ T ≤ 10
  • 2 ≤ N ≤ 105
  • 1 ≤ Ai ≤ 105

 

Output

For each testcase, print the required answer in one line.

 

Sample Input

2 2 7 2 3 2 2 4

Sample Output

2 -1
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
int t, n,k,ans;
int gcd(int x,int y)
{
    return y==0 ? x : gcd(y,x%y);
}

int main()
{
    cin>>t;
    while(t--){
    cin>>n;   cin>>ans;
    for (int i=2;i<=n;i++)//范围!
    {
        cin>>k;
        ans=gcd(ans,k);//递归!
    }
    if (ans==1) cout<<n<<endl; else cout<<"-1"<<endl;
    }
    return 0;
}