Cod sursa(job #1179689)

Utilizator MarianMMorosac George Marian MarianM Data 29 aprilie 2014 01:52:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int t, a, b, c;

void egcd(int a, int b, int & x, int & y){
	int i = 0;
	int r, q, v[][2] = {1, 0, 0, 1, 0, 0};

	do{
		q = a / b;	r = a % b;

		v[(i + 2) % 3][0] = v[i % 3][0] - q*v[(i + 1) % 3][0];
		v[(i + 2) % 3][1] = v[i % 3][1] - q*v[(i + 1) % 3][1];

		a = b;	b = r;	i++;
	} while (r);

	x = v[i % 3][0];	y = v[i % 3][1];
}

int gcd(int a, int b){
	if (!b) 
		return a;
	else 
		return gcd(b, a%b);
}

int main(){
	int g, x, y;

	fin >> t;
	for (; t; t--){
		fin >> a >> b >> c;
		g = gcd(a, b);
		if (c %  g == 0){
			x = 0; y = 0;
			if (b){
				egcd(a, b, x, y);
				fout << x * (c / g) << ' ' << y * (c / g)<< '\n';
			}
			else{
				fout << "1 0\n";
			}
		}
		else{
			fout << "0 0\n";
		}
	}

	return 0;
}