Cod sursa(job #523206)

Utilizator Rares95Rares Arnautu Rares95 Data 17 ianuarie 2011 14:06:50
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream.h>
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
long long n,a,b,c,d,i,s,t;

long long euclidextins(long long a, long long b, long long &s, long long &t)
{	long long 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;
	}
	s=s2; t=t2;
	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;
}