蓝桥杯 差分数组
对差分数组求最大公约数
要特判差值为 0 的情况 否则会错一个点
// 对差分数组求最大公约数
// 注意 gcd 函数在 vs 系的编辑器过不去,记得复习下辗转相除
// 要特判差值为 0 的情况 否则会错一个点
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int>array(n);
for (int i = 0; i < n; i++) {
cin >> array[i];
}
sort(array.begin(), array.end());
vector<int>diff(n - 1);
for (int i = 1; i < n; i++) {
diff[i - 1] = array[i] - array[i - 1];
}
// 注意结果是差分得到的值加一 因为差分少算了一个开头
int ans = 1;
int getGCD = diff[0];
for (int i = 0; i < n - 1; i++) {
// 特判差值为 0
if (getGCD == 0) {
ans++;
getGCD = diff[i];
} else {
getGCD = gcd(getGCD, diff[i]);
}
}
for (auto i : diff) {
// 特判
if (i == 0) {
continue;
}
ans += i / getGCD;
}
cout << ans << endl;
return 0;
}