Cod sursa(job #780831)

Utilizator crushackPopescu Silviu crushack Data 22 august 2012 01:25:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>

typedef long long ll;
const char IN[]="euclid3.in",OUT[]="euclid3.out";

int Tes,A,B,C;

int gcd(int a,int b,ll &x,ll &y){
	if (b==0)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		int ret=gcd(b,a%b,x,y);
		ll aux;
		aux=x;
		x=y;
		y=aux-y*(a/b);
		return ret;
	}
}

int main()
{
	freopen(IN,"r",stdin);
	scanf("%d",&Tes);
	freopen(OUT,"w",stdout);
	while (Tes--)
	{
		ll x,y;
		scanf("%d%d%d",&A,&B,&C);
		int d=gcd(A,B,x,y);
		if (C%d)
			printf("0 0\n");
		else
		{
			d=C/d;
			printf("%lld %lld\n",x*d,y*d);
		}
	}
	fclose(stdout);
	fclose(stdin);
	return 0;
}