Cần tìm giá trị ~C + D~ nhỏ nhất sao cho ~(A + C) * X = (B + D) * Y~.

Nhận xét: ~C~ tăng thì ~D~ tương ứng cũng tăng. Do đó chỉ cần tìm được ~C_{min}~ mà ~D~ tương ứng thỏa mãn là một số nguyên không âm.

Cô lập ~D~ của phương trình ban đầu, ta được: ~D = \frac{(A + C) * X}{Y} - B~.

Với giới hạn ~A, B, X, Y~ tương đối nhỏ ta có thể duyệt ~C~ để tìm ~C_{min}~ thỏa mãn ~D~ là một số nguyên không âm, cũng là ~C + D~ nhỏ nhất của bài toán.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

void process() {
    int A, B, X, Y;
    cin >> A >> B >> X >> Y;

    for(int C = 0; C <= 10000; ++C) {

        if(((A + C) * X) % Y != 0) continue;

        int D = ((A + C) * X) / Y - B;

        if(D >= 0) {
            cout << C + D << "\n";
            return;
        }

    }
    cout << -1 << "\n";
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);

    int tests;
    cin >> tests;

    while(tests--) 
        process();

    return 0;
}