Cod sursa(job #651447)

Utilizator razielreaperMatei Andrei razielreaper Data 20 decembrie 2011 14:08:32
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <cstdio>

long euclid(long a, long b, long &x, long &y) {
    if ( b==0 ) {
        x = 1,  y = 0;
        return a;
    }
    long xp, yp;
    long d = euclid(b, a%b, xp, yp);
    x = yp;
    y = xp - yp*(a/b);
    return d;
}

long T;

int main() {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    scanf("%ld", &T);
    while ( T-- ) {
        long a,b,c,d,x,y;
        scanf("%ld %ld %ld", &a, &b, &c);

        d = euclid(a, b, x, y);
        if ( c%d )
            printf("0 0\n");
        else
            printf("%ld %ld\n", x*(c/d), y*(c/d));
    }
    return 0;
}