Cod sursa(job #583576)

Utilizator Catah15Catalin Haidau Catah15 Data 20 aprilie 2011 23:59:53
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>

using namespace std;


inline int gcd (int A, int B, int &X, int &Y)
{
	if (! B)
	{
		X = 1;
		Y = 0;
		return A;
	}
	
	int x0, y0;
	
	int D = gcd (B, A % B, x0, y0);
	Y = x0 - (A / B) * y0;
	X = y0;
	
	return D;
}


int main()
{
	freopen ("euclid3.in", "r", stdin);
	freopen ("euclid3.out", "w", stdout);
	
	int T;
	
	scanf ("%d", &T);
	
	while (T --)
	{
		int a, b, c, X, Y;
		
		scanf ("%d %d %d", &a, &b, &c);
		
		int D = gcd (a, b, X, Y);
		
		if (c % D) printf ("0 0\n");
		else printf ("%d %d\n", X * (c / D), Y * (c / D));
	}
	
	return 0;
}