INTEGER7 - Số nguyên

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

using namespace std;

#define int long long

int bezout(int a, int b) {
    int xa = 1, xb = 0;
    while (b) {
        int q = a / b;
        int r = a - q * b, xr = xa - q * xb;
        a = b; xa = xb;
        b = r; xb = xr;
    }
    return xa;
}

int solve(int a, int b, int c) {
    int g = __gcd(a, b);
    int x = bezout(a, b) * (c / g);
    int p = abs(b / g), q = abs(a / g);
    x = (x % p + p) % p;
    int y = (c - a * x) / b;
    int cur = x + y;
    if (x < 0 || y < 0) cur = -1;
    int yy = (y % q + q) % q;
    int xx = (c - b * yy) / a;
    if (cur == -1 || (min(xx, yy) >= 0 && cur > xx + yy))
        cout << xx << ' ' << yy << endl;
    else
        cout << x << ' ' << y << endl;
}

main() {
    int a1, a2, b1, b2;
    cin >> a1 >> b1 >> a2 >> b2;
    solve(a1, -a2, b2 - b1);
}

Download