ZCMU Problem E: Subarray GCD（n个数的最大公约数）
<center>
Submit: 44 Solved: 27
[Submit][Status][Web Board] </center>
Problem E: Subarray GCD
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 44 Solved: 27
[Submit][Status][Web Board] </center>
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;
}
查看18道真题和解析