Cod sursa(job #2713302)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 27 februarie 2021 17:33:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

struct math {
  int Tgcd(int a, int b) {
    if (b == 0) {
      return a;
    } else {
      return Tgcd(b, a % b);
    }
  }
  int d = 0;
  pair<int, int> gcd(int a, int b) {
    if (b == 0) {
      d = a;
      return {1, 0};
    } else {
      pair<int, int> it = gcd(b, a % b);
      return {it.second, it.first - a / b * it.second};
    }
  }
  pair<int, int> coef(int a, int b, int c) {
    auto it = gcd(a, b);
    if (c % d) return {0, 0};
    it.first *= (c / d);
    it.second *= (c / d);
    return it;
  }
};

math user;

signed main() {
  freopen ("euclid3.in", "r", stdin), freopen ("euclid3.out", "w", stdout);
  int t;
  cin >> t;
  while (t--) {
    int a, b, c;
    cin >> a >> b >> c;
    auto it = user.coef(a, b, c);
    cout << it.first << " " << it.second << "\n";
  }
}