Cod sursa(job #2222766)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 18 iulie 2018 00:18:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>

using namespace std;

void euclid(long long A, long long B, long long &X, long long &Y, long long &D)
{
    if (!B) {
        X = 1;
        Y = 0;
        D = A;
        return;
    }
    long long X0, Y0;
    euclid(B, A % B, X0, Y0, D); /// B * X0 + (A - [A/B]*B) * Y0 = D
    X = Y0;
    Y = X0 - (A / B) * Y0;
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    int T;
    cin >> T;
    while (T --) {
        long long A,B,C;
        cin >> A >> B >> C;
        long long X, Y, D;
        euclid(A, B, X, Y, D);
        if (C % D == 0) {
            cout << X * C / D << " " << Y * C / D << "\n";
        }
        else
            cout << "0 0\n";
    }

    return 0;
}