Cod sursa(job #149134)

Utilizator crusRus Cristian crus Data 5 martie 2008 12:51:55
Problema Algoritmul lui Euclid extins Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#define input "euclid3.in"
#define output "euclid3.out"
long cmmdc(long a,long b)
{
 if (a%b) return cmmdc(b,a%b);
    else return b;
}
void euclid(long long a,long long b,long long *d,long long *x,long long *y)
{
 if (b==0)
    {
     *d=*x;
     *x=1;
     *y=0;
    }
    else
    {
     long x0,y0;
     euclid(b,a%b,d,&x0,&y0);
     *x=y0;
     *y=x0-(a/b)*y0;
    }
}
long t,a,b,c,x,y,d;
int main()
{
 FILE *fin=fopen(input,"r"), *fout=fopen(output,"w");
 fscanf(fin,"%ld",&t);
 while (t--)
       {
	fscanf(fin,"%ld %ld %ld",&a,&b,&c);
	euclid(a,b,&d,&x,&y);
	if (c%cmmdc(a,b))
	   fprintf(fout,"0 0\n");
	   else
	   {
	   x=(x*c)/(cmmdc(a,b));
	   y=(y*c)/(cmmdc(a,b));
	   d=cmmdc(a,b);
	   while (x<-2000000000)
		 {
		  x+=b/d;
		  y-=a/d;
		 }
	   while (x>2000000000)
		 {
		  x-=b/d;
		  y+=a/d;
		 }
	   while (y<-2000000000)
		 {
		  x-=b/d;
		  y+=a/d;
		 }
	   while (y>2000000000)
		 {
		  x+=b/d;
		  y-=a/d;
		 }
	   fprintf(fout,"%ld %ld\n",x,y);
	   }
       }
 fclose(fout);
 fclose(fin);
 return 0;
}