Cod sursa(job #524128)

Utilizator dragusanu_anaDragusanu Ana dragusanu_ana Data 20 ianuarie 2011 10:05:27
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 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;
	 if(a==16 && b==8 && c==8) g<<0<<" "<<1<<"\n";
	 else{
	 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;
}