Cod sursa(job #2725829)

Utilizator preda.andreiPreda Andrei preda.andrei Data 19 martie 2021 18:50:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdint>
#include <fstream>
#include <utility>

using namespace std;

int64_t Gcd(int64_t a, int64_t b) {
    while (b != 0) {
        auto m = a % b;
        a = b;
        b = m;
    }
    return a;
}

pair<int64_t, int64_t> Euclid(int64_t a, int64_t b) {
    if (b == 0) {
        return {1, 0};
    }

    auto xy = Euclid(b, a % b);
    return {xy.second, xy.first - a / b * xy.second};
}

pair<int64_t, int64_t> Solve(int64_t a, int64_t b, int64_t c) {
    auto gcd = Gcd(a, b);
    if (c % gcd != 0) {
        return {0, 0};
    }

    auto xy = Euclid(a, b);
    auto factor = c / gcd;
    return {xy.first * factor, xy.second * factor};
}

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

    int n;
    fin >> n;

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

        auto res = Solve(a, b, c);
        fout << res.first << " " << res.second << "\n";
    }
    return 0;
}