Cod sursa(job #144712)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 27 februarie 2008 21:24:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<stdio.h>
long t,a,b,c,x,y,r,aa,bb,d;
void rec(long a,long b,long *d,long *x,long *y)
{long x0,y0;
 if(b==0)
   {
    *d=a;
    *x=1;
    *y=0;
   }
     else
   {
    rec(b,a%b,d,&x0,&y0);
    *x=y0;
    *y=x0-(a/b)*y0;
   }
}
int main()
{
 freopen("euclid3.in","r",stdin);
 freopen("euclid3.out","w",stdout);
 scanf("%ld",&t);
 for(t=t;t>=1;--t)
    {scanf("%ld%ld%ld",&a,&b,&c);
     aa=a;
     bb=b;
     while(bb)
      {r=aa%bb;
       aa=bb;
       bb=r;
      }
     d=aa;
     rec(a,b,&d,&x,&y);
     if(c%aa==0) printf("%ld %ld\n",x*(c/aa),y*(c/aa));
	    else printf("0 0\n");
    }
 return 0;
}