Cod sursa(job #206567)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 7 septembrie 2008 19:00:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <stdio.h>

void GCDE(int a, int b, int &x, int &y, int &d)
{
	if (b == 0) {
		x = 1, y = 0, d = a;
		return;
	} 
	
	int x0, y0;
	GCDE(b, a % b, x0, y0, d);
	x = y0;
	y = x0 - y0 * (a / b);
}

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

	int T, a, b, c, x, y, cc;
	for (scanf("%d\n", &T); T; T --) {
		scanf("%d %d %d\n", &a, &b, &c);

		GCDE(a, b, x, y, cc);
		if (c % cc) printf("0 0\n");
		else printf("%d %d\n", x * (c / cc), y * (c / cc));
	}

	return 0;
}