Cod sursa(job #657178)

Utilizator ionicaion ionica Data 5 ianuarie 2012 21:42:54
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
using namespace std;
long x1,x2,x3;
long yy1,y2,y3;
long r1,r2,r3;

long cmmdc(long a,long b)
{
	if(b==0)return a;
	if(a%b==0)return b;
	return cmmdc(b,a%b);
}

int main()
{
	long a,b,c,e,d,u,w,c1,c2,c3,i,n,j,sa,sb;
	ifstream f("euclid3.in");
	ofstream g("euclid3.out");
	f>>n;
	for(j=1;j<=n;j++)
	{f>>a>>b>>c;
	sa=sb=1;
	if(a<0){sa=-1;a=-a;}
	if(b<0){sb=-1;b=-b;}
	 d=cmmdc(a,b);
	 if(c%d!=0)g<<"0 0\n";
	 else 
	  {if(a%b==0){u=0;w=1;}
	   else 
	     {e=a%b;
	     if(b%e==0){u=1;w=-a/b;}
	   	 else{r1=a%b;c1=a/b;
              x1=1;yy1=-c1;
		      r2=b%r1;
			  c2=b/r1;
			  x2=-c2;
			  y2=1+c1*c2;
			  i=2;
			  do{i++;
			     c3=r1/r2;
			     r3=r1%r2;
				 if(r3==0)break;
				 x3=x1-c3*x2;
				 y3=yy1-c3*y2;
				 
				 x1=x2;x2=x3;
				 yy1=y2;y2=y3;
				 
				 r1=r2;r2=r3;
				 
			    }while(1);
			  u=x2; w=y2;
		     }
		 }
	  u=u*(c/d); w=w*(c/d);
	  u=u*sa;
	  w=w*sb;
	  g<<u<<' '<<w<<'\n';
	  }
	}
}