Cod sursa(job #1092212)

Utilizator pulseOvidiu Giorgi pulse Data 26 ianuarie 2014 18:53:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <cstdio>

using namespace std;

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

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

int main ()
{
	freopen ("euclid3.in", "r", stdin);
	freopen ("euclid3.out", "w", stdout);
	scanf ("%d", &t);
	for (; t; --t)
	{
		scanf ("%d %d %d", &a, &b, &c);
		Euclid (a, b, d, x, y);
		if (c % d != 0) printf ("0 0\n");
		else printf ("%d %d\n", x * (c / d), y * (c / d));
	}
	return 0;
}