Cod sursa(job #586431)

Utilizator fricCalin Paul Alexandru fric Data 1 mai 2011 06:10:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <stdio.h>

int tests, a, b, c;
int d, x, y;

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

	int x0, y0, d;
	d = euclizi(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);
	scanf("%d", &tests);
	
	while (tests)
	{
		scanf("%d %d %d", &a, &b, &c);
		d = euclizi(a, b, x, y);
		
		if (c % d)
			printf("0 0\n");
		else
			printf("%d %d\n", x*(c/d), y*(c/d));
		
		tests--;
	}

	return 0;
}