Cod sursa(job #143318)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 26 februarie 2008 11:54:00
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <stdio.h>

int a, b, c, t, d, x, y;

int gcd(int A, int B, int &X, int &Y )
{
	int X0, Y0, D;
    if (!B)
    {
        X = 1;
        Y = 0;
        return A;
    }

    D = gcd( B, A % B, X0, Y0 );
    
    X = Y0;
    Y = X0 - (A / B) * Y0;
    return D;
}
 
int main()  
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);

	scanf("%d",&t);
    while (t--)
    {
        scanf("%d %d %d", &a, &b, &c);
        d = gcd( a, b, x, y );
        
        if (c % d) printf("0 0\n");
        else  printf("%d %d\n", x * (c / d), y * (c / d));
    }
    return 0;
}