Cod sursa(job #1333499)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 3 februarie 2015 11:26:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>

using namespace std;

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

long long a, b, c, x, y, D, T, i;
long long cmmdc(long long a, long long b){
    long long c;
    while(b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
void euclid(long long &x, long long &y, long long a, long long b){
    if(b == 0)
        {
            x = 1;
            y = 0;
        }
    else
    {
    long long x0,y0;
    euclid(x0, y0, b, a % b);
    x = y0;
    y = x0 - (a / b) * y0;
    }

}
int main()
{
    fin >> T;
    for(i = 1; i <= T; i ++)
    {
        fin >> a >> b >> c;
        D = cmmdc (a , b);
        if(c % D != 0)
            fout << "0 0\n";
        else
        {
            euclid(x,y,a,b);
            fout << x * (c / D) << " " << y * (c / D) << '\n';
        }
    }
    return 0;
}