Cod sursa(job #2723070)

Utilizator Iulia25Hosu Iulia Iulia25 Data 13 martie 2021 15:29:57
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>

using namespace std;

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

pair <int, int> euclid_extins(int a, int b) {
  if (b == 0)
    return {1, 0};
  pair <int, int> aux = euclid_extins(b, a % b);
  int x = aux.second;
  int y = aux.first - a / b * aux.second;
  return {x, y};
}

int cmmdc(int a, int b)  {
  if (b == 0)
    return a;
  int r = a % b;
  while (r) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

int main()  {
  int t, a, b, c;
  cin >> t;
  while (t--) {
    cin >> a >> b >> c;
    int d = cmmdc(a, b);
    if (c % d)  {
      cout << "0 0\n";
      continue;
    }
    pair <int, int> ans = euclid_extins(a, b);
    cout << ans.first * (c / d) << ' ' << ans.second * (c / d) << '\n';
  }
  return 0;
}