Cod sursa(job #396614)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 15 februarie 2010 17:43:17
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <stdio.h>
void cmmdc(int a, int b,int &d, int &x, int &y){
	if(b == 0){
		d = a;
		x = 1;
		y = 0;
		return;
	}
	int x0, y0;
	cmmdc(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);
	int t;
	scanf("%d", &t);
	for(;t ;--t){
		int a, b, c, d, x, y;
		scanf("%d%d%d", &a, &b, &c);
		cmmdc(a, b, d, x, y);
		if(c % d)
			printf("0 0\n");
		else printf("%d %d\n", x * (c/d), y * (c/d));
	}
	return 0;
}