Cod sursa(job #626696)

Utilizator irene_mFMI Irina Iancu irene_m Data 27 octombrie 2011 22:21:25
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#define infile "euclid3.in"
#define outfile "euclid3.out"

int T,A,B,C,D,X,Y;

int Euclid(int A, int B, int &X, int &Y)
{
    int X0, Y0, D;

    if(!B)
    {
        X = 1;
        Y = 0;
        return A;
    }

    D = Euclid(B, A % B, X0, Y0);
    X = Y0;
    Y = X0 - ( A / B ) * Y0;
    return D;
}

int main()
{
    freopen(infile,"r",stdin);
    freopen(outfile,"w",stdout);

    scanf("%d", &T);
    for( ; T; T--)
    {
        scanf("%d %d %d",&A, &B, &C);
        D = Euclid( A, B, X, Y);

        if(C % D)
            printf("0 0\n");
        else
            printf("%d %d\n", X * ( C / D ), Y * ( C / D ) );
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}