Cod sursa(job #2449481)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 19 august 2019 21:44:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

ll g;
pair <ll, ll> gcd(ll a, ll b) {
  if (b == 0) {
    g = a;
    return {1, 0};
  } else {
    pair <ll, ll> aux = gcd(b, a % b);
    return {aux.second, aux.first - (ll)a / b * aux.second};
  }
}

int main() {
  freopen ("euclid3.in","r",stdin);
  freopen ("euclid3.out","w",stdout);

  int t;
  cin >> t;

  while (t--) {
    ll a, b, c;
    cin >> a >> b >> c;
    pair <ll, ll> aux = gcd(a, b);
    if (c % g)
      cout << "0 0\n";
    else
      cout << aux.first*(c / g) << " " << aux.second*(c / g) << "\n";
  }


  return 0;
}