Cod sursa(job #3265587)

Utilizator susanSusan Ssssss susan Data 1 ianuarie 2025 00:19:38
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>

using namespace std;
using ll = long long;

ll gcd(const ll a, const ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    ll x0, y0;
    const ll d = gcd(b, a % b, x0, y0);
    x = y0;
    y = x0 - a / b * y0;
    return d;
}


int main() {
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");

    int t;
    f >> t;
    while (t--) {
        ll a, b, c;
        f >> a >> b >> c;
        if (ll x, y, d = gcd(a, b, x, y); c % d != 0) g << "0 0\n";
        else g << x * (c / d) << ' ' << y * (c / d) << '\n';
    }
}