Cod sursa(job #716758)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 19 martie 2012 10:53:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <fstream>
#include <algorithm>
using namespace std;
typedef struct{
int x,y,d;
} elem;
elem euclid(int a,int b)
{
	elem e;
	if(b==0) 
	{
		e.d=a; e.x=1; e.y=0;
		return e;
	}
	e=euclid(b,a%b);
	swap(e.x,e.y);
	e.y-=e.x*(a/b);
	return e;
	
}
int main()
{
	int t,a,b,c;
	elem e;
	ifstream fi("euclid3.in");
	ofstream fo("euclid3.out");
	fi>>t;
	while(t--)
	{
		fi>>a>>b>>c;
		e=euclid(a,b);
		if(c%e.d) fo<<"0 0\n"; else	fo<<e.x*(c/e.d)<<" "<<e.y*(c/e.d)<<"\n";
	}
	return 0;
}