Cod sursa(job #1443482)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 27 mai 2015 23:47:13
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <cassert>
#define _submit
#ifdef _submit
#define InFile "euclid3.in"
#define OutFile "euclid3.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned short ushort;

class pair {
public:
	LL x, y;
	pair operator*(LL a) {
		return{ x*a, y*a };
	}
	pair operator-(pair &p2) {
		return{ this->x - p2.x, this->y - p2.y };
	}
};

pair euclidExtins(LL a, LL b, LL c) {
	pair s = { 1, 0 }, t = { 0, 1 };
	while (b) {
		LL q = a / b;
		LL r = a % b;
		pair pr = s - t*q;
		a = b;
		b = r;
		s = t;
		t = pr;
	}
	if (c % a)
		return{ 0, 0 };
	return s*(c / a);
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OutFile, "w", stdout));
	LL T;
	scanf("%lld", &T);
	while (T--) {
		LL a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		pair P = euclidExtins(a, b, c);
		printf("%lld %lld\n", P.x, P.y);
	}
	return 0;
}