Cod sursa(job #519657)

Utilizator titeltitel popescu titel Data 6 ianuarie 2011 08:54:38
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<fstream>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int a,b,c,s,t,d,e,T,i;
int euclidextins(int a, int b, int &s, int &t){
	int r,q, s1, t1, s2, t2;
	if(b==0) {s=1; t=0; return a;}
	else{
		s1=1; s2=0; t1=0; t2=1;
		r=a%b; q=a/b;
		while(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(){
	f>>T;
	for(i=1;i<=T;++i){
		f>>a>>b>>c;
		d=euclidextins(a,b,s,t);
		if(c%d) g<<"0 0"<<"\n";
		else {e=c/d; g<<s*e<<" "<<t*e<<"\n";}
	}
	g.close(); return 0; 
}