Cod sursa(job #2237727)

Utilizator Ionut228Ionut Calofir Ionut228 Data 2 septembrie 2018 20:16:00
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <bits/stdc++.h>

using namespace std;

void gcd_extended(int a, int b, int& d, int& x, int& y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0; // any value
  } else {
    int x0, y0;
    gcd_extended(b, a % b, d, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
  }
}

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

  int t, a, b, c;
  cin >> t;

  while (t--) {
    cin >> a >> b >> c;
    int d, x, y;
    gcd_extended(a, b, d, x, y);

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

  return 0;
}