Cod sursa(job #1268447)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 20 noiembrie 2014 22:44:27
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

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

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

    return 0;
}