Cod sursa(job #466513)

Utilizator whoasdas dasdas who Data 26 iunie 2010 21:04:52
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;
inline void calc(long &a,long &b,long &rez, ofstream & out)
{
	if(b==0)
		out<<0<<" "<<0<<"\n";
	else
	{
		long a1,a2,a3,b1,b2,b3,c2,c3,d1,d2,d3;
		
		a1 = 1; a2 = 0; b1 = 0; b2 = 1; d1 = a; d2 = b; c2 = a/b;
		
		while(1)
		{
			d3 = d1 % d2;
			if(d3==0) break;
			a3 = a1 - a2 * c2;
			b3 = b1 - b2 * c2;
			c3 = d2 / d3;

			a1 = a2; b1 = b2; d1 = d2;
			a2 = a3; b2 = b3; c2 = c3; d2 = d3;
		}
		
		if((rez/d2)*d2 != rez)
			out<<0<<" "<<0<<"\n";
		else out<<a2*(rez/d2)<<" "<<b2*(rez/d2)<<"\n";
	}
}
int main()
{
	long n,i,j,a,b,c;
	ifstream in("euclid3.in");
	ofstream out("euclid3.out");
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>a>>b>>c;
		calc(a,b,c,out);
	}

	out.close();
	return 0;
}