CodeChef Sharing Candies

問題

Contest Page | CodeChef

整数 A, B, C, D が与えられる。

abs( (A+p*C) - (B+q*D) ) を最小化するように p, q(p, q >= 0) を取った場合の, abs の値を求めよ。

解法

これは超典型的で, C, D の最大公約数 g に対して, abs(A+g*p - B) (p は任意の整数) としたときの最小値を求めればよいだけです。

ll solve() {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    {
        ll mini = min(A, B);
        A -= mini;
        B -= mini;
    }
    if (A > B) {
        swap(A, B);
        swap(C, D);
    }
    ll g = __gcd(C, D);
    ll q = B%g;
    return min(q, g-q);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cout << solve() << endl;
    }
    return 0;
}