Cod sursa(job #2974491)

Utilizator Cezar_RusuCezar Rusu Cezar_Rusu Data 4 februarie 2023 09:57:44
Problema Algoritmul lui Euclid extins Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <cstdlib>

typedef long long int llint;

void euclid(llint, llint, llint &, llint &, llint &);

int n;
llint a, b, c, d, x, y;

int main() { int i;
  std::FILE *input, *output; input = std::fopen("euclid3.in", "r"), output = std::fopen("euclid3.out", "w");

  std::fscanf(input, "%d", &n);
  for (i = 0; i < n; ++i) {
    std::fscanf(input, "%lld%lld%lld", &a, &b, &c);
    euclid(a, b, d, x, y);
    if (c % d) std::fprintf(output, "0 0\n");
    else std::fprintf(output, "%lld %lld\n", x*(c/d), y*(c/d));
  }

  std::fclose(output);
  return 0;
}

void euclid(llint a, llint b, llint &d, llint &x, llint &y) {
  if (b == 0) { d = a; x = 1, y = 1; }
  else { llint x0, y0; euclid(b, a%b, d, x0, y0); x = y0, y = x0 - (a/b) * y0; }
}