Cod sursa(job #2640556)

Utilizator trifangrobertRobert Trifan trifangrobert Data 6 august 2020 20:21:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

int gcdExtended(int A, int B, int &X, int &Y)
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }
    int X0, Y0, D;
    D = gcdExtended(B, A % B, X0, Y0);
    X = Y0;
    Y = X0 - A / B * Y0;
    return D;
}

int main()
{
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    int tests;
    fin >> tests;
    while (tests-- > 0)
    {
        int A, B, C, D, X, Y;
        fin >> A >> B >> C;
        D = gcdExtended(A, B, X, Y);
        if (C % D)
            fout << "0 0\n";
        else
            fout << X * (C / D) << " " << Y * (C / D) << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}