题目描述

    There is an array of length n, containing only positive numbers.

    Now you can add all numbers by  many times.

    Please find out the minimum times you need to perform to obtain an array whose greatest common divisor(gcd) is larger than  or state that it is impossible.

    You should notice that if you want to add one number by , you need to add all numbers by  at the same time.

输入

    The first line of input file contains an integer T (≤T≤), describing the number of test cases.

    Then there are ×T lines, with every two lines representing a test case.

    The first line of each case contains a single integer n (≤n≤1e5) described above.

    The second line of that contains n integers ranging in [,1e9].

输出

    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 - instead.

样例输入

样例输出

Case :

Case : -

Case : 

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int maxn=1e5+;

 int n;

 int a[maxn];

 int GCD(int _a,int _b)

 {

     return _a ==  ? _b:GCD(_b%_a,_a);

 }

 ll Solve()

 {

     sort(a+,a+n+);

     int t=unique(a+,a+n+)-a;

     t--;

     if(t == )///情况①

         return a[] ==  ? :;

     ll gcd=a[]-a[];

     for(int i=;i <= t;++i)

         gcd=GCD(gcd,a[i]-a[i-]);

     if(gcd == )///情况(2.1)

         return -;

     ll ans=(a[]/gcd+(a[]%gcd ==  ? :))*gcd-a[];///情况(2.2)

     for(ll i=;i*i <= gcd;++i)

     {

         if(gcd%i != )

             continue;

         ll j=gcd/i;

         ///找到最小的 curAns 使得所有数 +curAns 都可以变为 i,j 的倍数

         ll curAns=(a[]/i+(a[]%i ==  ? :))*i-a[];

         curAns=min(curAns,(a[]/j+(a[]%j ==  ? :))*j-a[]);

         ans=min(ans,curAns);

     }

     return ans;

 }

 int main()

 {

     int test;

     scanf("%d",&test);

     for(int kase=;kase <= test;++kase)

     {

         scanf("%d",&n);

         for(int i=;i <= n;++i)

             scanf("%d",a+i);

         printf("Case %d: %lld\n",kase,Solve());

     }

     return ;

 }

 比赛的时候，只考虑了使所有的数都变成gcd的最小的因子的倍数的情况；

 并没有考虑到所有数变成gcd的其他因子的倍数使得答案最小；

 赛后，吃完午饭美美的睡上了一觉；

 午睡刚醒，就看到队友zyd给我发的G题ac的截图；

 一脸懵逼的我问了句为啥？？？？

 例如

     差值为21

     21的非1的因子有3,,

     所有数都变成3的倍数需要 +

     所有数都变成7的倍数需要 +

     所有数都变成21的倍数需要 +

     答案当然是1啦，所以说，最优解不一定是变成gcd最小因子的倍数