Cod sursa(job #522326)

Utilizator Rares95Rares Arnautu Rares95 Data 14 ianuarie 2011 20:47:11
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include<fstream.h>
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int n,a,b,c,d,e,i,s,t;

int euclidextins(int a, int b, int &s, int &t)
{	int r,q,s1,s2,t1,t2;
	if(!b) {s=1; t=0; return a;}
	s1=1; s2=0; t1=0; t2=1;
	r=a%b; q=a/b;
	for(;r;)
	{	s=s1-s2*q; s1=s2; s2=s;
		t=t1-t2*q; t1=t2; t2=t;
		a=b; b=r; r=a%b; q=a/b;
	}
	return b;
}

int main()
{	fin>>n;
	for(;n;--n)
	{	fin>>a>>b>>c;
		d=euclidextins(a,b,s,t);
		if(c%d) fout<<"0 0"<<'\n';
		else {c/=d; fout<<c*s<<" "<<c*t<<'\n';}
	}
	fout.close(); return 0;
}