Cod sursa(job #352469)

Utilizator capmIonut Vasilescu capm Data 1 octombrie 2009 22:37:57
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <algorithm>

#define x first
#define y second

using namespace std;

pair<long long, long long> gcd_e(long long a, long long b)
{
	pair<long long, long long> ret, temp;
	if(b == 0)
	{
		return make_pair((long long)1, (long long)0);
	}
	temp = gcd_e(b, a % b);
	ret.x = temp.y;
	ret.y = temp.x - ret.x * (a / b);
	return ret;
}


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

	int t;
	long long a, b, c, d;
	pair<long long, long long> ret;

	for(scanf("%d", &t); t; --t)
	{
		scanf("%lld %lld %lld", &a, &b, &c);
		ret = gcd_e(a, b);
		d = a * ret.x + b * ret.y;

		if(c % d != 0)
		{
			printf("0 0\n");
		}
		else
		{
			ret.x *= c/d;
			ret.y *= c/d;
			while(ret.x > 2000000000 || ret.y < -2000000000)
			{
				ret.x -= b/d * c;
				ret.y += a/d * c;
			}

			while(ret.x < -2000000000 || ret.y > 2000000000)
			{
				ret.x += b/d * c;
				ret.y -= a/d * c;
			}
			printf("%lld %lld\n", ret.x, ret.y);
		}

	}

	return 0;
}