Cod sursa(job #184782)

Utilizator raduzerRadu Zernoveanu raduzer Data 24 aprilie 2008 12:12:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <stdio.h>

int n,i,a,b,c,x,y,d;

void euclid ( int a, int b, int *d, int *x, int *y ) 
{   
    if (b == 0) 
	{   
        *d = a;   
        *x = 1;   
        *y = 0;   
    } else {   
        int x0, y0;   
        euclid(b, a % b, d, &x0, &y0);   
        *x = y0;   
        *y = x0 - (a / b) * y0;   
    }   
}   

int main()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; ++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		euclid(a,b,&d,&x,&y);
		if (c%d==0) printf("%d %d\n",x*(c/d),y*(c/d));   
        else printf("0 0\n");
	}
	return 0;
}