Cod sursa(job #523588)

Utilizator Codrutzu15tapu codrut Codrutzu15 Data 18 ianuarie 2011 16:57:38
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 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;
}