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

我不是女神ヾ 2022-01-06 07:33 188阅读 0赞

#  #

Greatest Common Divisor

## [题目链接][Link 1] ##

## 题目描述 ##

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);
        }
    }

转载于:https://www.cnblogs.com/llke/p/10816655.html