Cod sursa(job #2466517)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 2 octombrie 2019 14:34:49
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>

using namespace std;

struct EuclidExtins {
  int x;
  int y;
};

int gcd(int a, int b) {
  while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
  }
  return a;
}

EuclidExtins euclid_extins(int a, int b, int d) {
  if (b == 0)
    return {d / a, 0};
  else {
    EuclidExtins lastSol = euclid_extins(b, a % b, d);
    int c = a / b;
    return {lastSol.y, lastSol.x - c * lastSol.y};
  }
}

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;
    scanf("%d%d%d", &a, &b, &c);

    // a * x + b * y = d

    int d = gcd(a, b);
    if (c % d == 0) {
      EuclidExtins sol = euclid_extins(a, b, d);
      int k = c / d;
      printf("%d %d\n", sol.x * k, sol.y * k);
    } else {
      printf("0 0\n");
    }
  }
  return 0;
}