Cod sursa(job #2445013)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 2 august 2019 11:04:38
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>

using namespace std;

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

int extendedGcd(int A, int B, int &x, int &y)
{
    if(B == 0) {

        x = 1, y = 0;
        return A;

    }

    int d, x0, y0;
    d = extendedGcd(B, A % B, x0, y0);
    x = y0;
    y = x0 - y0 * (A / B);

    return d;
}

int main()
{
    int T; fin >> T;

    for(int i = 1; i <= T; i++) {

        int A, B, C, D, x, y;

        fin >> A >> B >> C;
        D = extendedGcd(A, B, x, y);

        if(C % D == 0)
            fout << x * (C / D) << ' ' << y * (C / D) << '\n';
        else
            fout << "0 0\n";
    }

    return 0;
}