Cod sursa(job #2575968)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 6 martie 2020 16:30:48
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>

using namespace std;

struct EuclidExtins {
  int x;
  int y;
};

EuclidExtins euclid_extins(int a, int b) {
  if (b == 0)
    return {1, 0};

  EuclidExtins lst;
  lst = euclid_extins(b, a % b);

  return {lst.y, lst.x - (a / b) * lst.y};
}

int cmmdc(int a, int b) {
  int r;
  while (b > 0) {
    r = a % b;
    a = b;
    b = r;
  }

  return a;
}

int main() {
  freopen("euclid3.in", "r", stdin);
  freopen("euclid3.out", "w", stdout);

  int t;
  scanf("%d", &t);
  for (int T = 0; T < t; T++) {
    int a, b, c, d;
    scanf("%d%d%d", &a, &b, &c);
    d = cmmdc(a, b);
    if (c % d != 0)
      printf("0 0\n");
    else {
      EuclidExtins e;
      e = euclid_extins(a, b);
      printf("%d %d\n", e.x * (c / d), e.y * (c / d));
    }
  }

  return 0;
}