Cod sursa(job #143334)

Utilizator filipbFilip Cristian Buruiana filipb Data 26 februarie 2008 12:38:36
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, x, y, d;

void gcd(int &x, int &y, int &d, int a, int b)
{
	if (!b)
		d = a, x = 1, y = 0;
	else
	{
		int aux;
		
		gcd(x, y, d, b, a % b);
		aux = x;
		x = y;
		y = aux - y * (a / b);
	}	
}

int main(void)
{
	int T;

	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	
	for (scanf("%d", &T); T; T--)
	{
		scanf("%d %d %d", &A, &B, &C);
		gcd(x, y, d, A, B);
		if (C % d)
			printf("0 0\n");
		else
			printf("%d %d\n", x * (C/d), y * (C/d));		
	}	
	
	return 0;
}