Cod sursa(job #616878)

Utilizator psycho21rAbabab psycho21r Data 13 octombrie 2011 16:36:45
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream in("euclid3.in");
    long n, a, b, c, x1, x2, y1, y2, q, temp;
    ofstream out("euclid3.out");
    in >> n;

    for (;n;--n)
    {
        in >> a >> b >> c;
        x1 = 0; y1 = 1;
        x2 = 1; y2 = 0;
        while (b)
        {
            //QUOTIENT
            q = a/b;

            //EUCLID
            temp = a;
            a = b;
            b = temp%b;
            //EUCLID

            //EXTENDED EUCLID
            temp = x1;
            x1 = x2 - q*x1;
            x2 = temp;

            temp = y1;
            y1 = y2 - q*y1;
            y2 = temp;
            //EXTENDED EUCLID
        }
        if (c%a == 0)
            out << x2*(c/a) << " " << y2*(c/a) << "\n";
        else
            out << "0 0";
    }

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

    return 0;
}