Cod sursa(job #808486)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 6 noiembrie 2012 20:12:57
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 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);
	int T = next_int();
	while (T--) {
		int a = next_int();
		int b = next_int();
		int c = next_int();
		int g = gcd(a, b);
		pair<int, int> eg = egcd(a, b);
		if (c % g == 0) {
			printf("%d %d\n", eg.first * c / g, eg.second * c / g);
		} else {
			printf("0 0\n");
		}
	}
	return 0;
}