Cod sursa(job #143368)

Utilizator DastasIonescu Vlad Dastas Data 26 februarie 2008 13:31:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>

FILE *in = fopen("euclid3.in","r"), *out = fopen("euclid3.out","w");

int t, a, b, c;

int euclid(int a, int b, int &c, int &d)
{
    if ( !b )
    {
        c = 1;
        d = 0;
        return a;
    }

    int c0, d0, dd;
    dd =  euclid(b, a % b, c0, d0);

    c = d0;
    d = c0 - (a / b) * d0;
    return dd;
}

int main()
{
    fscanf(in, "%d", &t);

    while ( t-- )
    {
        fscanf(in, "%d %d %d", &a, &b, &c);

        int d, x, y;
        d = euclid(a, b, x, y);

        if ( c % d )
            fprintf(out, "%d %d\n", 0, 0);
        else
            fprintf(out, "%d %d\n", x * ( c / d ), y * ( c / d ));
    }



	return 0;
}