题目描述
There is an array of length n, containing only positive numbers.
Now you can add all numbers by 1 many times. Please find out the minimum times you need to perform to obtain an array whose greatest common divisor(gcd) is larger than 1 or state that it is impossible.
You should notice that if you want to add one number by 1, you need to add all numbers by 1 at the same time.
Now you can add all numbers by 1 many times. Please find out the minimum times you need to perform to obtain an array whose greatest common divisor(gcd) is larger than 1 or state that it is impossible.
You should notice that if you want to add one number by 1, you need to add all numbers by 1 at the same time.
输入
The first line of input file contains an integer T (1≤T≤20), describing the number of test cases.
Then there are 2×T lines, with every two lines representing a test case.
The first line of each case contains a single integer n (1≤n≤105) described above.
The second line of that contains n integers ranging in [1,109].
Then there are 2×T lines, with every two lines representing a test case.
The first line of each case contains a single integer n (1≤n≤105) described above.
The second line of that contains n integers ranging in [1,109].
输出
You should output exactly T lines.
For each test case, print Case d: (d represents the order of the test case) first. Then output exactly one integer representing the answer. If it is impossible, print -1 instead.
For each test case, print Case d: (d represents the order of the test case) first. Then output exactly one integer representing the answer. If it is impossible, print -1 instead.
样例输入
复制样例数据
3
1
2
5
2 5 9 5 7
5
3 5 7 9 11
样例输出
Case 1: 0
Case 2: -1
Case 3: 1
提示
Sample 1: You do not need to do anything because its gcd is already larger than 1.
Sample 2: It is impossible to obtain that array.
Sample 3: You just need to add all number by 1 so that gcd of this array is 2.
题目大意：每次操作都给数组的所有数同时+1,问最少操作几次使得所有数的gcd大于1，或者压根不能使得所有数的gcd大于1。
思路类似于CF的Neko does Maths CodeForces - 1152C 数论欧几里得，不过这题的k是对n个数而言，但思路是一样的。
假设b>=a，我们知道gcd(a+k,b+k)是b-a的因子，那么要想知道所有都+k能不能有gcd>1，那就是得看两两数做差，看他们的差的gcd是不是大于1，但是两两做差O(n2）肯定不行。而我们把所有数排序，然后求相邻两个数的差的gcd,就可以了。因为，像三个数a,b,c，他们的差分别是d1,d2,如果d1和d2不互质，那么d1和d1+d2自然也不互质。得出gcd，我们就枚举gcd的因子就好了。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
int a[N];
int main()
{
int t=,T,n;
scanf("%d",&T);
while(t<=T)
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int g=,ans;
for(int i=;i<n;i++)//并不需要去重，因为gcd(0,x)=x
g=__gcd(g,a[i]-a[i-]);
if(g==)
ans=-;
else if(g==)//都是同一个数的时候得特判
{
if(a[]==)
ans=;
else
ans=;
}
else
{
ans=(g-a[]%g)%g;
for(int i=;i*i<=g;i++)//枚举因子，找最小答案
if(g%i==)
{
ans=min(ans,(i-a[]%i)%i);
ans=min(ans,(g/i-a[]%(g/i))%(g/i));
}
}
printf("Case %d: %d\n",t++,ans);
}
return ;
}
gcd