Cod sursa(job #658071)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 7 ianuarie 2012 21:06:59
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>

using namespace std;

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

int n, a, b, c, d;

int euclid(int a, int b)
{
	int r=a%b;
	
	while (r) a=b, b=r, r=a%b;
	
	return b;
}

void Euclid_extins(int a, int b, int c)
{
	int precx=1, precy=0, x=0, y=1, auxx, auxy, cat=a/b, r=a%b, w;
	
	while (r)
	{
		auxx=x*(-cat)+precx; auxy=y*(-cat)+precy;
		precx=x; precy=y;
		x=auxx; y=auxy;
		a=b;
		b=r;
		r=a%b;
		cat=a/b;
	}
	
	w=c/b;
	
	g<<x*w<<" "<<y*w<<"\n";
}

int main()
{
	f>>n;
	while (n--)
	{
		f>>a>>b>>c;
		
		d=euclid(a, b);
		
		if (c%d!=0) g<<"0 0\n";
			else Euclid_extins(a/d, b/d, c/d);
	}
	f.close();
	g.close();
	return 0;
}