Cod sursa(job #517772)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 29 decembrie 2010 19:55:28
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
long a,b,c,x,y,d;
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,&d,&x,&y);
              printf("%ld %ld\n",x*c/d,y*c/d);}}
fclose(stdin);
fclose(stdout);
return 0;}