例如序列的最大公约数为,的最大公约数为
现在牛牛想知道,对于一个长度为的序列,如果他至多能删除个数,请问他最少需要删除多少个数才能让序列的最大公约数变为,或者这根本是不可能的
第一行输入一个整数,表示数据组数
对于每组数据,
第一行输入一个整数
接下来一行个整数表示序列中的数
输出T个整数,若可能,则输出最少需要删除的数,若不可能,则输出-1
2 3 2 2 4 2 1 2
-1 0
对于第一个序列,可以证明,无论删除哪几个数,都无法使序列的gcd变为1对于第二个序列,不需要删除
对于的数据,
对于的数据,
#include <bits/stdc++.h>//ASI typedef long long ll; using namespace std; int n,t; int main() { ios::sync_with_stdio(0),cin.tie(0); int i,j,x,y; cin>>t; while(t--) { /**< 如果序列最大公约数不是1,那么删除数字不可能让公约数变小 */ cin>>n>>x; for(i=2;i<=n;i++) { cin>>y; x=__gcd(x,y); } if(x==1) cout<<0<<endl; else cout<<-1<<endl; } return 0; }