Cod sursa(job #449208)

Utilizator ionicaion ionica Data 5 mai 2010 21:29:24
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
using namespace std;
long x[10000],y[10000],r[10000];
long cmmdc(long a,long b)
{
	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{r[1]=a%b;c1=a/b;
              x[1]=1;y[1]=-c1;
		      r[2]=b%r[1];
			  c2=b/r[1];
			  x[2]=-c2;
			  y[2]=1+c1*c2;
			  i=2;
			  do{i++;
			     c3=r[i-2]/r[i-1];
			     r[i]=r[i-2]%r[i-1];
				 x[i]=x[i-2]-c3*x[i-1];
				 y[i]=y[i-2]-c3*y[i-1];
			    }while(r[i]!=0);
			  u=x[i-1]; w=y[i-1];
		     }
		 }
	  u=u*(c/d); w=w*(c/d);
	  u=u*sa;
	  w=w*sb;
	  g<<u<<' '<<w<<'\n';
	  }
	}
}