Cod sursa(job #1939416)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 25 martie 2017 18:34:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

using namespace std;

void gcd2(int &x, int &y, int a, int b)
{
    if(b == 0){
        x = 1;
        y = 0;
    }else{
        gcd2(x, y, b, a%b);
        int aux = x;
        x = y;
        y = aux - (a/b)*y;
    }
}

int gcd(int x, int y)
{
    if(y == 0)
        return x;
    return gcd(y, x%y);
}

int main()
{
    ifstream fin ("euclid3.in");
    ofstream fout ("euclid3.out");
    int t;
    fin >> t;
    while(t--){
        int a, b, d, x, y;
        fin >> a >> b >> d;
        int factor = gcd(a, b);
        if(d%factor != 0){
            fout << "0 0\n";
            continue;
        }
        factor = d / factor;
        gcd2(x, y, a, b);
        fout << x * factor << " " << y * factor << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}