题目链接: Greatest Common Divisor
大致题意 【历年真题|2018CCPC桂林站 G. Greatest Common Divisor (gcd 差分 质因数分解)】给定一个长度为 n n n的序列, 可以执行任意多次操作: 给所有位置的数值+1.
问: 最少执行多少次操作, 使得 g c d ( { a 1 , a 2 , . . . , a n } ) ≠ 1 gcd(\{ a_1, a_2, ..., a_n \}) \ne 1 gcd({a1?,a2?,...,an?})?=1. 若无解则输出 ? 1 -1 ?1.
解题思路 差分
这类区间加 且 求 g c d gcd gcd的题目, 我们比较容易的想到转化成差分的思路进行求解.
对于本题而言, 每次是使区间 [ 1 , n ] + 1 [1, n] + 1 [1,n]+1. 若设原序列为 a [ ] a[] a[], 差分序列为 b [ ] b[] b[]. 则操作等价于使得 b [ 1 ] + 1 , b [ n + 1 ] ? 1 b[1] + 1, b[n + 1] - 1 b[1]+1,b[n+1]?1. 对 n + 1 n + 1 n+1位置操作没有意义, 因此操作最终等价于: b[1] + 1.
现在问题变为, 至少进行多少次b[1] + 1操作, 使得 g c d ( { b 1 , b 2 , . . . , b n } ) ≠ 1 gcd(\{ b_1, b_2, ..., b_n \}) \ne 1 gcd({b1?,b2?,...,bn?})?=1.
我们易得: 如果 g c d ( { b 2 , b 3 , . . . , b n } ) = 1 gcd(\{b_2, b_3, ..., b_n\}) = 1 gcd({b2?,b3?,...,bn?})=1, 则无解.
质因数分解
反之, 设 d = g c d ( { b 2 , b 3 , . . . , b n } ) d = gcd(\{b_2, b_3, ..., b_n\}) d=gcd({b2?,b3?,...,bn?}). 相当于我们需要求 g c d ( b 1 , d ) ≠ 1 gcd(b_1, d) \ne 1 gcd(b1?,d)?=1的最小操作次数.
我们只需要让 b 1 b_1 b1?和 d d d有至少1个相同的质因子即可.
因此我们可以对 d d d进行质因数分解, 通过枚举所有结果, 取最小值即可.
AC代码
#include
#define rep(i, n) for (int i = 1;
i <= (n);
++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
int a[N], b[N];
int get(int d) { return (d - b[1] % d) % d;
}
int fact(int d) {
int res = INT_MAX;
for (int i = 2;
i <= d / i;
++i) {
if (d % i == 0) {
res = min(res, get(i));
while (d % i == 0) d /= i;
}
}
if (d > 1) res = min(res, get(d));
return res;
}
int main()
{
int t;
cin >> t;
rep(tt, t) {
int n;
scanf("%d", &n);
rep(i, n) scanf("%d", &a[i]), b[i] = abs(a[i] - a[i - 1]);
int d = 0;
for (int i = 2;
i <= n;
++i) d = gcd(d, b[i]);
if (d == 0) printf("Case %d: %d\n", tt, b[1] == 1);
else {
int res = fact(d);
printf("Case %d: %d\n", tt, res == INT_MAX ? -1 : res);
}
} return 0;
}
END
推荐阅读
- 总结|STL讲课讲义
- 算法|2020年10月份蓝桥杯省赛B组C++题解
- #|kuangbin线段树专题
- Codeforces|Codeforces940F Machine Learning (带修莫队)
- Codeforces|Codeforces126B Password (KMP)
- 总结|关于c++中的临时变量
- 蓝桥杯|2019蓝桥杯省赛C++A组真题解析
- 竞赛习题|蓝桥杯第十二届个人省赛C/C++B组（欢迎大家在底部评论留下自己疑问）
- 蓝桥杯|2018年蓝桥杯省赛 C++ B组