Cod sursa(job #1206970)

Utilizator sorin2kSorin Nutu sorin2k Data 11 iulie 2014 17:06:44
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<iostream>
using namespace std;

void extended_euclid(int a, int b, int &x, int &y) {
	if(b == 0) {
		x = 1;
		y = 0;
	} else {
		int x_aux, y_aux;
		extended_euclid(b, a % b, x, y);
		x_aux = x;
		y_aux = y;
		x = y_aux;
		y = x_aux - (a / b) * y_aux;
	}
}

int gcd(int a, int b) {
	if(b == 0) return a;
	int r = a % b;
	while(r) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int main() {
//	freopen("euclid3.in", "r", stdin);
//	freopen("euclid3.out", "w", stdout);
	int a, b, c, gd, x, y, t, i;
	cin >> t;
	for(i = 0; i < t; i++) {
		cin >> a >> b >> c;
		if(a == 0 && b == 0) {
			cout << "0 0\n";
			continue;
		}
		gd = gcd(a, b);
		if(c % gd == 0) {
			extended_euclid(a, b, x, y);
			cout << x * (c / gd) << " " << y * (c / gd) << '\n';
		} else {
			cout << "0 0\n";
		}
	}
	return 0;
}