Cod sursa(job #158135)

Utilizator znakeuJurba Andrei znakeu Data 13 martie 2008 14:31:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>

long long euclid(long long a, long long b, long long *x, long long *y)
{
    if (b == 0)
	{
        *x = 1;
        *y = 0;
		return a;
    }
    long long x0, y0, d;
    d=euclid(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);
	
	long long t=0,a=0,b=0,c=0,d=0,x=0,y=0;
	
	scanf("%lld",&t);
	
	while (t)
	{
		t--;
		scanf("%lld%lld%lld",&a,&b,&c);
		d=euclid(a,b,&x,&y);
		if (c%d)
			printf("0 0\n");
		else
			printf("%lld %lld\n",x*c/d,y*c/d);
	}
	
	fclose(stdin);
	fclose(stdout);	
	return 0;
}