Cod sursa(job #2077295)

Utilizator anisca22Ana Baltaretu anisca22 Data 27 noiembrie 2017 21:25:33
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>

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

int T;

int euclid(int A, int B, int &X, int &Y)
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return A;
    }

    int prevX, prevY;
    int D = euclid(B, A % B, prevX, prevY);
    X = prevY;
    Y = prevX - (A / B) * prevY;
    return D;
}

int main()
{
    fin >> T;
    while (T--)
    {
        int A, B, C;
        fin >> A >> B >> C;

        int X, Y;

        int D = euclid(A, B, X, Y);
        if (C % D != 0)
            X = Y = 0;
        fout << X * (C / D) << " " << Y * (C / D) << "\n";
    }
    return 0;
}