Cod sursa(job #2912394)

Utilizator EZ4ENCEAleksi Jalli EZ4ENCE Data 8 iulie 2022 11:25:18
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;

struct hatz {
  int x, y;
};

int srcval;

hatz euclid_extins(int a, int b) {
  if (b == 0) {
    /// ajung la ecuatia a * x = srcval
    if (srcval % a == 0)
      return {srcval / a, 0};
    return {0, 0};
  }

  int x, y;

  hatz valxy0 = euclid_extins(b, a % b);

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

int main() {
  ifstream cin ("euclid3.in");
  ofstream cout ("euclid3.out");

  int t, a, b;
  cin >> t;

  while (t--) {
    cin >> a >> b >> srcval;
    hatz sol = euclid_extins(a, b);
    cout << sol.x << " " << sol.y << "\n";
  }
  return 0;
}