Codeforces gym 102823G. Greatest Common Divisor 题解
题目大意
给 \(n\) 个数，每次可以给所有数加 \(1\) ，问最少需要多少次可以让所有数的 \(\text{gcd}(a_i)>1\)，若不存在则输出 \(-1\).
题解
有关最大公约数的性质：原数组的 \(\text{gcd}\) 和差分后的数组的 \(\text{gcd}\) 相等，于是我们把原输入数组差分，所以每次全部加一可以转化为只在差分数组 \(d[1]\) 上加，我们取 \(\_g=\text{gcd}(d_2,d_3,\cdots,d_n)\)，然后把 \(\_g\) 质因数分解，则可以通过模的同余系快速得到最少需要加 \(k\) 才可以使 \(d[1]\) 成为某一个质因数的倍数，所有质因数对应的 \(k\) 中最小的即为最终答案.
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
template <typename _Tp>
void write(_Tp a) {
if(a < 0) putchar('-'), a = -a;
if(a > 9) write(a / 10); putchar(a % 10 + '0');
}
const int N = 1e5 + 5;
int a[N], d[N];
int main() {
int T;
read(T);
const int INF = 1e9 + 5;
vector<int> p;
for(int _T = 1; _T <= T; _T++) {
p.clear();
int ans = INF;
int n;
read(n);
for(int i = 1; i <= n; i++) {
read(a[i]);
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) {
d[i] = a[i] - a[i - 1];
}
int _g = 0;
for(int i = 2; i <= n; i++) {
_g = __gcd(_g, d[i]);
}
if(!_g) {
if(d[1] == 1) ans = 1;
else ans = 0;
goto ed;
}
for(int i = 2; i <= _g / i; i++) {
if(_g % i == 0) {
p.push_back(i);
while(_g % i == 0) {
_g /= i;
}
}
}
if(_g > 1) {
p.push_back(_g);
}
for(auto x : p) {
int o = d[1] % x;
int tmp = x - o;
if(o == 0) tmp = 0;
ans = min(ans, tmp);
}
if(ans == INF) ans = -1;
ed: printf("Case %d: %d\n", _T, ans);
}
return 0;
}
|