【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e565
【解題想法】
- UVA原題是“not all numbers occuring in a sequence are equal“，不會發生所有數字都相等的情況。
- 整數序列 a[0], a[1], a[2], …, a[N-1] 要符合題意：
- a[0] = q[0] * d + r
- a[1] = q[1] * d + r
- a[2] = q[2] * d + r
- ….
- a[N-1] = q[N-1] * d + r
- 相鄰兩項相減，可移除 r。
- a[0] – a[1] = (q[0] – q[1]) * d
- a[1] – a[2] = (q[1] – q[2]) * d
- …
- a[N-2] – a[N-1] = (q[N-2] – q[N-1]) * d
- d 為 {a[0] – a[1], a[1] – a[2], …, a[N-2] – a[N-1]} 的GCD。
- 測資含負數，因此先對前述數列取絕對值。
- 數列中可能有相等的數字（兩項差值為零），計算GCD需要避免發生除以0。
#include <iostream>
#include <vector>
using namespace std;
int GCD(int x, int y){
if (!x) return y;
if (!y) return x;
while ((x%=y) && (y%=x));
return x+y;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int x;
while (cin >> x && x){
int a[1005];
int N = 1;
a[0] = x;
while (cin >> x && x){
a[N++] = x;
}
int d = abs(a[0] - a[1]);
for (int i = 1; i < N-1; i++){
d = GCD(d, abs(a[i] - a[i+1]));
}
cout << d << "\n";
}
return 0;
}