Cod sursa(job #715320)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 17 martie 2012 00:07:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb

#include <fstream>
using namespace std;

int cmmdc(long a,long b)
{
 long c;
 while (b != 0)
  {
   c = a % b;
   a = b;
   b = c;
  }
 return a;
}

void euclid(long a,long b,long *d,long *x,long *y)
{
 if (b == 0)
   {
    *d = a;
    *x = 1;
    *y = 0;
   }
  else
   {
    long nx,ny;
    euclid(b,a % b,d,&nx,&ny);
    *x = ny;
    *y = nx - (a / b) * ny;
   }
}

int main(void)
{
 fstream fin("euclid3.in",ios::in);
 fstream fout("euclid3.out",ios::out);
 long T,a,b,i,c,d,x,y;
 fin >> T;
 for (i = 0;i < T;i += 1)
  {
   fin >> a >> b >> c;
   euclid(a,b,&d,&x,&y);
   if ((c % d) != 0)
     {
      fout << "0 0\n";
      continue;
     }
   fout << (x * (c / d)) << " " << (y * (c / d)) << "\n";
  }
 fin.close();
 fout.close();
 return 0;
}