CCPC2018 桂林 G "Greatest Common Divisor"(数学)

UPC备战省赛组队训练赛第十七场

            with zyd,mxl

G: Greatest Common Divisor

CCPC2018 桂林  G "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≤1e5) described above.
    The second line of that contains n integers ranging in [1,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 -1 instead.
题目描述 CCPC2018 桂林  G "Greatest Common Divisor"(数学)
样例输入
3

1
2

5
2 5 9 5 7

5
3 5 7 9 11

样例输出
Case 1: 0
Case 2: -1
Case 3: 1
样例输入输出

题意:

  定义a[]数组存储输入的 n 个数;

  求使得 ∀i∈[1,n] GCD(a[i]+x) > 1 的最小的 x;

  如果不存在这样的x,输出-1;

思路:

  将数组 a 排序,去重;

  ①去重后,如果只有一个元素,输出 (a[1] == 1 ? 1:0);

  ②找到相邻两数差值的GCD记为gcd:

    (2.1)如果 gcd == 1 ,输出 -1

    (2.2)反之,所有数肯定可以通过增加 x 使得所有数变为 gcd 的倍数,当然也可以变为gcd因子的倍数,

      求解出最小的x输出;

AC代码:

CCPC2018 桂林  G "Greatest Common Divisor"(数学)
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=1e5+50;
 5 
 6 int n;
 7 int a[maxn];
 8 
 9 int GCD(int _a,int _b)
10 {
11     return _a == 0 ? _b:GCD(_b%_a,_a);
12 }
13 ll Solve()
14 {
15     sort(a+1,a+n+1);
16     int t=unique(a+1,a+n+1)-a;
17     t--;
18     if(t == 1)///情况①
19         return a[1] == 1 ? 1:0;
20 
21     ll gcd=a[2]-a[1];
22     for(int i=2;i <= t;++i)
23         gcd=GCD(gcd,a[i]-a[i-1]);
24 
25     if(gcd == 1)///情况(2.1)
26         return -1;
27     ll ans=(a[1]/gcd+(a[1]%gcd == 0 ? 0:1))*gcd-a[1];///情况(2.2)
28     for(ll i=2;i*i <= gcd;++i)
29     {
30         if(gcd%i != 0)
31             continue;
32         ll j=gcd/i;
33         ///找到最小的 curAns 使得所有数 +curAns 都可以变为 i,j 的倍数
34         ll curAns=(a[1]/i+(a[1]%i == 0 ? 0:1))*i-a[1];
35         curAns=min(curAns,(a[1]/j+(a[1]%j == 0 ? 0:1))*j-a[1]);
36         ans=min(ans,curAns);
37     }
38     return ans;
39 }
40 int main()
41 {
42     int test;
43     scanf("%d",&test);
44     for(int kase=1;kase <= test;++kase)
45     {
46         scanf("%d",&n);
47         for(int i=1;i <= n;++i)
48             scanf("%d",a+i);
49 
50         printf("Case %d: %lld\n",kase,Solve());
51     }
52     return 0;
53 }
View Code

总结:

CCPC2018 桂林  G "Greatest Common Divisor"(数学)
 1 比赛的时候,只考虑了使所有的数都变成gcd的最小的因子的倍数的情况;
 2 并没有考虑到所有数变成gcd的其他因子的倍数使得答案最小;
 3 赛后,吃完午饭美美的睡上了一觉;
 4 午睡刚醒,就看到队友zyd给我发的G题ac的截图;
 5 一脸懵逼的我问了句为啥????
 6 例如
 7     13 34
 8     差值为21
 9     21的非1的因子有3,7,21
10     所有数都变成3的倍数需要 +2
11     所有数都变成7的倍数需要 +1
12     所有数都变成21的倍数需要 +8
13     答案当然是1啦,所以说,最优解不一定是变成gcd最小因子的倍数
View Code

 

上一篇:数栈SQL优化案例:OR条件优化


下一篇:python_restframework(认证组件)