Cod sursa(job #2972131)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 ianuarie 2023 18:19:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <memory>

using namespace std;

class Solver{
 private:
  int N;
 public:
  Solver() {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
  }
  ~Solver() {
    fclose(stdin);
    fclose(stdout);
  }
  void readData() {
    scanf("%d", &N);
  }
  void extendedEuclid(long long A, long long &X, long long B, long long &Y, long long &D) {
    if (B == 0) {
      // GCD(A, 0) = A
      // A * 1 + B * 0 = GCD(A,B)
      // A * 1 + 0 * 0 = A
      D = A;
      X = 1;
      Y = 0;
      return;
    }
    long long _X, _Y;
    extendedEuclid(B, _X, A%B, _Y, D);
    // B * _X + (A-[A/B]*B) * _Y = D
    // A * X + B * Y = D
    X = _Y;
    Y = _X -A/B*_Y;
  }
  void computeAnswers() {
    long long A, X, B, Y, D, C;
    for (int i = 0; i < N; ++i) {
      scanf("%lld%lld%lld", &A, &B, &C);
      extendedEuclid(A, X, B, Y, D);
      /// A*X + B*Y = D
      /// A*X*C + B*Y*C = D*C
      /// (A*X*C)/D + (B*Y*C)/D = C
      /// A*((X*C)/D) + B*((Y*C)/D) = C
      if((X*C) % D == 0 && (Y*C) % D == 0)
	printf("%lld %lld\n", X*C/D, Y*C/D);
      else
	printf("0 0\n");
    }
  }
};

int main()
{
  unique_ptr<Solver> s = make_unique<Solver>();
  s->readData();
  s->computeAnswers();
  return 0;
}