Cod sursa(job #1326721)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 25 ianuarie 2015 21:30:37
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;

int d;

void gcd(int a, int b, int & x, int & y) {

    if(b == 0) {
        x = 1;
        y = 0;
        d = a;
    } else {
        gcd(b, a % b, x, y);

        int aux = x;
        x = y;
        y = aux - (a / b) * y;
    }
}

int main() {

    int a, b, c, x, y, queries;

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

    in >> queries;
    while(queries--) {

        in >> a >> b >> c;
        gcd(a, b, x, y);

        if(c % d != 0)
            out << "0 0\n";
        else
            out << (x * (c / d)) << ' ' << (y * (c / d)) << '\n';
    }

    in.close();
    out.close();

    return 0;
}