Cod sursa(job #658080)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 7 ianuarie 2012 21:15:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 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";
}

void Trateaza(int a, int b, int c)
{
	int aux, ok=0;
	if (b==0) aux=a, a=b, b=aux, ok=1;
	
	if (c%b!=0) g<<"0 0";
	else 
		if (ok) g<<c/b<<" 0\n";
			else g<<"0 "<<c/b<<"\n";
}


int main()
{
	f>>n;
	while (n--)
	{
		f>>a>>b>>c;
		
		if (a==0 || b==0) Trateaza(a, b, c);
		else
		{
			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;
}