Cod sursa(job #1127148)

Utilizator Sirius2001Happy Birthday Sirius2001 Data 27 februarie 2014 11:22:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
/*
    Keep It Simple!
*/

#include<stdio.h>

void super_euclid(int a,int b,int *d,int *x,int *y)
{
   if(!b)
   {
     *d = a;
     *x = 1;
     *y = 0;
   }
   else
   {
      int x0,y0;
      super_euclid(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);

   int a,b,d,T,x,y,dp;

   scanf("%d",&T);
   for(int i=1;i<=T;i++)
   {
      scanf("%d%d%d",&a,&b,&d);
      super_euclid(a,b,&dp,&x,&y);
      if( d % dp != 0 )
      {
        x = 0;
        y = 0;
      }
      else
      {
          int multiplu = d/dp;
          x *= multiplu;
          y *= multiplu;
      }

      printf("%d %d\n",x,y);
   }
}