Cod sursa(job #2930526)

Utilizator matthriscuMatt . matthriscu Data 28 octombrie 2022 16:49:50
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <bits/stdc++.h>
using namespace std;

pair<int, int> euclid(int a, int b) {
    if (!b)
        return {1, 0};

    auto [x0, y0] = euclid(b, a % b);
    return {y0, x0 - a / b * y0};
}

int32_t main() {
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");

    int n;
    fin >> n;

    for (int i = 1, a, b, c; i <= n; ++i) {
        fin >> a >> b >> c;

        int d = __gcd(a, b);

        if (c % d != 0) {
            fout << "0 0\n";
            continue;
        }

        auto [x, y] = euclid(a, b);
        fout << x * (c / d) << ' ' << y * (c / d) << '\n';
    }
}