【題解】ZeroJudge e565: 10407 – Simple division

【題目敘述】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;
}
分享本文 Share with friends