Cod sursa(job #1331952)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 1 februarie 2015 14:07:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

int d;

int main() {

    int a, b, c, q, xOld, yOld, x, y, aux, T;

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

    in >> T;

    while(T--) {

        in >> a >> b >> c;

        y = xOld = 1;
        x = yOld = 0;

        while(b) {

            q = a / b;

            // gcd
            aux = b;
            b = a % b;
            a = aux;
            // x & y
            aux = x;
            x = xOld - q * aux;
            xOld = aux;

            aux = y;
            y = yOld - q * aux;
            yOld = aux;
        }

        // gcd
        d = a;
        x = xOld;
        y = yOld;

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

        }

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

    return 0;

}