Cod sursa(job #2606355)

Utilizator daria_stoianStoian Daria Alexandra daria_stoian Data 27 aprilie 2020 16:15:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>

using namespace std;
int euclid( int a, int b ){
  if ( b == 0 ){
    return a;
  }
  return euclid(b, a%b);
}
void euclid_e(int a, int b, int &x, int &y, int &d){
  if ( b == 0 ){
    d = a;
    x = 1;
    y = 0;
    return;
  }
  int xx, yy, q = a/b;
  euclid_e(b, a%b, xx, yy, d);
  x = yy;
  y = xx - yy*q;
}
int main()
{
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    int a, b, c, d, x, y, r, t, i;
    fin >> t;
    i = 0;
    while ( i < t ){
      fin >> a >> b >> c;
      d = euclid(a,b);
      euclid_e(a, b, x, y, d);
      if ( c % d != 0 ){
        fout << "0 0\n" ;
      }
      else{
        fout << (c/d)*x << " " << (c/d)*y << "\n";
      }
      i++;
    }
    fin.close();
    fout.close();
    return 0;
}