Cod sursa(job #2462125)

Utilizator preda.andreiPreda Andrei preda.andrei Data 26 septembrie 2019 19:43:54
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>

using namespace std;

int Gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    return Gcd(b, a % b);
}

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

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

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

    auto res = Euclid(a, b);
    return {1LL * res.first * d / gcd, 1LL * res.second * d / gcd};
}

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

    int tests;
    fin >> tests;

    for (int i = 0; i < tests; i += 1) {
        int a, b, d;
        fin >> a >> b >> d;

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