upc组队赛17 Greatest Common Divisor【gcd+最小质因数】

时间：2022-04-23 09:53:34

Greatest Common Divisor

题目链接

题目描述

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.

输入

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

输出

Please output T lines exactly.

For each line, output Case d: (d represents the order of the test case) first. Then output the answer in the same line. If there is no way for that, 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；

然后找到gcd的最小质因数g ，操作的次数为距离a[0]最近的g的倍数-a[0]； 即g - a[0] % g;

还有其他各种特判，在代码中说明

代码

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,n) for(int i=a;i<n;i++)

#define scac(x) scanf("%c",&x)

#define sca(x) scanf("%d",&x)

#define sca2(x,y) scanf("%d%d",&x,&y)

#define sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scl(x) scanf("%lld",&x)

#define scl2(x,y) scanf("%lld%lld",&x,&y)

#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pri(x) printf("%d\n",x)

#define pri2(x,y) printf("%d %d\n",x,y)

#define pri3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prl(x) printf("%lld\n",x)

#define prl2(x,y) printf("%lld %lld\n",x,y)

#define prl3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define mst(x,y) memset(x,y,sizeof(x))

#define ll long long

#define LL long long

#define pb push_back

#define mp make_pair

#define P pair<double,double>

#define PLL pair<ll,ll>

#define PI acos(1.0)

#define eps 1e-6

#define inf 1e17

#define mod 1e9+7

#define INF 0x3f3f3f3f

#define N 1005

const int maxn = 1e5+10;

ll a[maxn],b[maxn];

ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

int n;

int  main()

{

    int t;

    sca(t);

    int cas = 1;

    while(t--)

    {

        sca(n);

        rep(i,0,n)  scl(a[i]);

        if(n == 1) //如果只有一个数

        {

            if(a[0] == 1) printf("Case %d: 1\n",cas++);

            else  printf("Case %d: 0\n",cas++);

            continue;

        }

        sort(a,a+n);

        int cnt = 0;

        rep(i,1,n)

        {

            if(a[i] != a[i-1]) //如果数相同就跳过

                b[cnt++] = a[i] - a[i-1];

        }

        if(cnt == 0)//如果所有数都相同

        {

            if(a[0] == 1) printf("Case %d: 1\n",cas++);

            else  printf("Case %d: 0\n",cas++);

            continue;

        }

        ll g = b[0];

        rep(i,1,cnt)  g = gcd(g,b[i]);

        if(g == 1) //不可能的情况

        {

            printf("Case %d: -1\n",cas++);

            continue;

        }

        if(gcd(g,a[0]) > 1) g = gcd(g,a[0]);

        rep(i,2,100000)

        {

          if(g % i == 0)

          {

            g = i;

            break;

          }

        }

        ll ans;

        if(a[0] % g) ans = g - a[0] % g;

        else ans = 0;

        printf("Case %d: %lld\n",cas++,ans);

    }

}

相关文章