Cod sursa(job #2959188)

Utilizator smunteanuMunteanu Stefan Catalin smunteanu Data 30 decembrie 2022 00:58:45
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 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) == 0) {
    auto [d, x, y] = euclidExtins(a, b);
    cout << x * (c / d) << ' ' << y * (c / d) << '\n';
  } else cout << "0 0\n";
}

int main() {
  freopen("euclid3.in", "r", stdin);
  freopen("euclid3.out", "w", stdout);
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) solve();
}