题解 CF1593D1 All are Same
智子
2021-10-14 23:55:13
## 题意
输入 $n$ 个数 $a_1,a_2,...a_n$，每次操作可以将一个数减小 $k$，若干次操作后所有的数的值全部相同，求 $k$ 的最大值。如果 $k$ 可以任意大，输出 $-1$。
## 思路
将一个数 $a$ 不断减去相同的数 $k$ 之后，变为另一个数 $b$ ，$k$ 显然是 $|b - a|$ 的约数，拓展到 $n$ 个数后同样成立。
所以题目中所求的 $k$ 就是 $\gcd(a_1 - a_2, a_2 - a_3, a_3 - a_4,... a_{n - 1} - a_n)$，即对差分求最大公约数。
## 代码
```cpp
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int MAXN = 40 + 5;
int a[MAXN];
int n;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int T;
cin >> T;
while(T--) {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 0;
for(int i = 2; i <= n; i++) {
ans = gcd(ans, a[i] - a[i - 1]);
}
if(ans < 0) {
ans = -ans;
}
if(ans == 0) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
```