Cod sursa(job #1478549)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 28 august 2015 22:22:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>

using namespace std;

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

int extendedEuclid(int a, int b, int *x, int *y){
	if (b==0){
		*x = 1;
		*y = 0;
		return a;
	}
	else{
		int gcd,x0,y0;
		gcd = extendedEuclid(b, a%b, &x0, &y0);
		*x = y0;
		*y = x0 - a/b * y0;
		return gcd;
	}
}

int main(void){
	
	int t;
	int a,b,c,x,y;
	in >> t;
	for (;t>0;t--){
		in >> a>>b>>c;
		int gcd=extendedEuclid(a, b, &x, &y);
		if (c%gcd==0) {
			int factor = c/gcd;
			out << x*factor << " " << y*factor << "\n";
		}
		else out << "0 0\n";
	}
	
	return 0;
}