Cod sursa(job #523610)

Utilizator Codrutzu15tapu codrut Codrutzu15 Data 18 ianuarie 2011 17:33:31
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<fstream.h>
ifstream f("euclid3.in");
ofstream g("euclid3.out");
short t;
int i,x,y,xp,yp;
long d,e,a,b,c;
long euclid(long a, long b, int &xx, int &yy)
{int r,x1,x2,y1,y2,q;
 if(b==0){xx=1; yy=0; return a;}
 else{r=a%b; q=a/b; x1=1; x2=0;
	  y1=0;y2=1;
	 while(r) 
		{ 
		  xx=x1-x2*q; x1=x2; x2=xx;
		  yy=y1-y2*q; y1=y2; y2=yy;
		  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;
	 x=0; y=0; xp=0;yp=0;
	 d=euclid(a,b,x,y);
	 if(c%d!=0) g<<0<<" "<<0<<"\n";
		else {e=c/d;x*=e;y*=e; g<<x<<" "<<y<<"\n";}
		}
	 

 g.close();
 return 0;
}