Cod sursa(job #517778)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 29 decembrie 2010 20:12:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>
long a,b,c,x,y,d,g,e;
int t,i;

void euclid1(long a,long b,long *d)
{if(b==0)
      (*d)=a;
else
      euclid1(b,a%b,d);}

void euclid2(long a,long b,long *d,long *x,long *y)
{long x0,y0;   
if(b==0) 
      {(*d)=a;
      (*x)=1;
      (*y)=0;} 
else 
      {euclid2(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("%d",&t);
for(i=1;i<=t;i++)
      {scanf("%ld%ld%ld",&a,&b,&c);
      euclid1(a,b,&d);
      if(c%d!=0)
              printf("0 0\n");
      else
              {euclid2(a,b,&e,&x,&y);
              g=c/d;
              printf("%ld %ld\n",x*g,y*g);}}
fclose(stdin);
fclose(stdout);
return 0;}