Cod sursa(job #654779)

Utilizator andunhillMacarescu Sebastian andunhill Data 30 decembrie 2011 21:36:19
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
using namespace std;

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

int T;
int x, y, gcd;

void euclid(int a, int b)
{	int x1, y1, x2, y2;
	int r, q;
	
	if(b == 0)
	{	x = 1;
		y = 0;
		gcd = a;
		return;
	}
	
	q = a / b;
	r = a % b;
	x2 = 1; y2 = 0;
	x1 = 0; y1 = 1;
	x = 0; y = 0;
	
	while(r)
	{	x = x2 - q * x1;
		y = y2 - q * y1;
		
		x2 = x1; y2 = y1;
		x1 = x; y1 = y;
		
		gcd = r;
		a = b; b = r;
		q = a / b;
		r = a % b;
	}
}

int main()
{	int i, a, b, c;
	
	f>>T;
	for(i = 1; i <= T; i++)
	{	f>>a>>b>>c;
		euclid(a, b);
		
		if(c % gcd) g<<"0 0"<<'\n';
		else g<<x * c / gcd<<" "<<y * c / gcd<<'\n';
	}
	
	f.close();
	g.close();
	return 0;
}