Cod sursa(job #2930516)

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

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

    pair<int, int> ans0 = euclid(b, a % b);
    return {ans0.second, ans0.first - a / b * ans0.second};
}

int 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;
        }

        pair<int, int> ans = euclid(a, b);
        fout << ans.first * c / d << ' ' << ans.second * c / d << '\n';
    }
}