Cod sursa(job #589844)

Utilizator voyagerSachelarie Bogdan voyager Data 13 mai 2011 23:57:10
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstdio>
#include <hash_set>
#include <algorithm>
#include <regex>

using namespace std;

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

int gcd(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}

	int xx, yy;
	int d = gcd(b, a % b, xx, yy);

	x = yy;
	y = xx - (a / b) * yy;

	return d;
}

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

	scanf("%d", &T);

	while (T--) {
		scanf("%d %d %d", &a, &b, &c);
		
		d = gcd(a, b, x, y);

		if (c % d) {
			puts("0 0");
		} else {
			printf("%d %d\n", x * (c / d), y * (c / d));
		}
	}

	fclose(stdout);
	fclose(stdin);
	return 0;
}