Cod sursa(job #1344853)

Utilizator cristian.enciuCristian Enciu cristian.enciu Data 17 februarie 2015 00:23:58
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<stdio.h>

int cmmdc(int a, int b, int& x, int& y)
{
	if(b == 0) {
		x = 1;
		y = 0;
		return a;
	}

	int x0, y0, d;
	d = cmmdc(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);

	int i;
	for(scanf("%d", &i) ; i > 0 ; --i){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		int d, x, y;
		
		d = cmmdc(a, b, x, y);

		if(c%d) {
			printf("0 0\n");
		} else {
			printf("%d %d\n", x * (c/d), y * (c/d));
		}
	}

	return 0;
}