Cod sursa(job #660366)

Utilizator RobertBBadea Corneliu Robert RobertB Data 12 ianuarie 2012 18:31:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.49 kb
#include <fstream>
using namespace std;

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

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

}

int main() 
{
	int T;
	
	f1>>T;
	for(;T ;T--) {
		int a,b,c,d,x,y;
		f1>>a>>b>>c;
		euc_ext(a ,b ,d ,x ,y);
		if(c%d)
			f2<<"0 0\n";
		else
			f2<<x*(c/d)<<" "<<y*(c/d)<<"\n";
	}
}