Cod sursa(job #2689620)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 21 decembrie 2020 17:43:49
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

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

int n;

pair<int, int> extendedGCD(int a, int b) {
    if(a < b) swap(a, b);

    int x, y, x0, y0;

    if(b) {
        pair<int, int> sol = extendedGCD(b, a % b);
        x0 = sol.first, y0 = sol.second;
        x = y0, y = x0 - (a/b) * y0;

        return {x, y};
    }

    return {1, 0};
}

int main()
{
    fin >> n;

    while(n--) {
        int a, b, c, d;
        fin >> a >> b >> d;

        pair<int, int> sol = extendedGCD(a, b);
        int x = sol.first, y = sol.second;
        c = a * x + b * y;

        if(d % c == 0) {
            fout << x * (d / c) << " " << y * (d / c) << '\n';
        } else {
            fout << "0 0\n";
        }
    }
    return 0;
}