Cod sursa(job #2959186)

Utilizator smunteanuMunteanu Stefan Catalin smunteanu Data 30 decembrie 2022 00:54:32
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

auto euclidExtins(int a, int b) {
  struct Euclid { int d, x, y; };
  if (b == 0) return Euclid{a, 1, 0};
  auto [d, x, y] = euclidExtins(b, a % b);
  return Euclid{d, y, x - (a / b) * y};
}

void solve() {
  int a, b, c;
  cin >> a >> b >> c;
  if (c % __gcd(a, b)) {
    cout << "0 0\n";
    return;
  } else {
    auto [d, x, y] = euclidExtins(a, b);
    int r1 = x * (c / d), r2 = y * (c / d);
    cout << r1 << ' ' << r2 << endl;
    // printf("%d * %d + %d * %d = %d\n", a, r1, b, r2, c);
    // printf("%d + %d = %d\n", a * r1, b * r2, c);
    // printf("%d = %d\n", a * r1 + b * r2, c);
  }
}

int main() {

  #ifdef LOCAL
  freopen("file.in", "r", stdin);
  #else
  freopen("euclid3.in", "r", stdin);
  freopen("euclid3.out", "w", stdout);
  #endif

  // ios_base::sync_with_stdio(false), cin.tie(NULL);

  int t;
  cin >> t;
  while (t--) solve();
}