Cod sursa(job #2637120)

Utilizator andreic06Andrei Calota andreic06 Data 21 iulie 2020 14:00:43
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>

using namespace std;

/// ax + by = d == cmmdc ( a, b );

void gcd_extins ( int a, int b, int *x, int *y, int *d ) {

    if ( b == 0 )
      *d = a, *x = 1, *y = 0;
    else {
      int xx, yy;
      gcd_extins ( b, a % b, &xx, &yy, d );
      *x = yy;
      *y = xx - ( a / b ) * yy;
    }
}

ifstream fin ( "euclid3.in" );
ofstream fout ( "euclid3.out" );

int main()
{
   int n, a, b, c;
   int cmmdc, x, y;
   fin >> n;
   for ( int i = 1; i <= n; i ++ ) {

      fin >> a >> b >> c;
      gcd_extins ( a, b, &x, &y, &cmmdc );
      if ( c % cmmdc )
        fout << 0 << ' ' << 0;
      else
        fout << x * ( c / cmmdc ) << ' ' << y * ( c / cmmdc );
      fout << '\n';
   }
    return 0;
}