Cod sursa(job #449466)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 6 mai 2010 12:57:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream.h>
//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;
//	if(a<0){sa=-1;a=-a;}
 // 	if(b<0){sb=-1;b=-b;}
	if (b==0)
		if (c%a==0)g<<c/a<<" 0\n";
		else g<<"0 0\n";
	else
	{
	 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';
	  }
	}
	}
}