Cod sursa(job #808489)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 6 noiembrie 2012 20:15:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <algorithm>
using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

template<class T> pair<T, T> egcd(T a, T b) {
	pair<T, T> x(0, 1), y(1, 0), g(a, b);
	while (g.second != 0) {
		T q = g.first / g.second;
		g = pair<T, T> (g.second, g.first % g.second);
		x = pair<T, T> (x.second - q * x.first, x.first);
		y = pair<T, T> (y.second - q * y.first, y.first);
	}
	return pair<T, T> (x.second, y.second);
}

template<class T> T gcd(T a, T b) {
	while (b != 0) {
		T t = a % b;
		a = b;
		b = t;
	}
	return a;
}

int main() {
	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);
	long long T = next_int();
	while (T--) {
		long long a = next_int();
		long long b = next_int();
		long long c = next_int();
		long long g = gcd(a, b);
		pair<int, int> eg = egcd(a, b);
		if (c % g == 0) {
			printf("%lld %lld\n", eg.first * c / g, eg.second * c / g);
		} else {
			printf("0 0\n");
		}
	}
	return 0;
}