Cod sursa(job #534877)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 16 februarie 2011 13:45:58
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <stdio.h>

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

inline int euclid(int A, int B, int &X, int &Y)
{
	if (B==0){
		X=1; Y=0; return A;
	}
	int auxx, auxy, D;
	D = euclid(B, A%B, auxx, auxy);
	X = auxy;
	Y = auxx - (A/B)*auxy;
	return D;
}

int main()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);

	for (scanf("%d",&T); 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", (C/D)*X, (C/D)*Y);
	}

	return 0;
}