Cod sursa(job #3213948)

Utilizator v_mateiVatamanu Matei v_matei Data 13 martie 2024 17:08:50
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <iostream>
#include <string>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>

#define IO (std::string) "euclid3"
std::ifstream cin(IO + ".in");
std::ofstream cout(IO + ".out");

int gcd(int A, int B, int &X, int &Y) {
  if (B == 0) {
    X = 1;
    Y = 0;
    return A;
  }

  int X0, Y0, D;
  D = gcd(B, A % B, X0, Y0);

  X = Y0;
  Y = X0 - (A / B) * Y0;
  return D;
}

void solve() {
  int a, b, c;
  cin >> a >> b >> c;
  int x, y, d;
  d = gcd(a, b, x, y);

  if (c % d == 0) {
    cout << x * (c / d) << ' ' << y * (c / d) << '\n';
  } else
    cout << 0 << ' ' << 0;
}

int main() {
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}