Cod sursa(job #2756647)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 2 iunie 2021 11:20:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;

void extendedEuclid(long long A, long long B, long long &X, long long &Y, long long &D)
{ // A*X + B*Y = D 
  if (!B) {
    D = A;
    X = 1;
    Y = 0;
    return;
  }

  long long _X, _Y;
  extendedEuclid(B, A % B, _X, _Y, D);
  // B * _X + (A - [A/B]*B) * _Y = D
  X = _Y;
  Y = _X - A/B * _Y;
}

int main()
{
  ifstream fin("euclid3.in");
  ofstream fout("euclid3.out");
  
  fin.sync_with_stdio(false);
  fin.tie(0);

  int N;
  fin >> N;
  for (int i = 0; i < N; ++i) {
    long long A, B, C, X, Y, D;

    fin >> A >> B >> C;
    extendedEuclid(A, B, X, Y, D);
    // A*X + B*Y = D and we want A*X' + B*Y' = C
    if (C % D != 0)
      fout << "0 0\n";
    else
      fout << X * (C/D) << " " << Y * (C/D) << "\n"; 
  }
  

  return 0;
}