Cod sursa(job #1492068)

Utilizator ELHoriaHoria Cretescu ELHoria Data 27 septembrie 2015 01:49:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <vector>
#include <functional>

using namespace std;

tuple<int, int, int> euclid(int a, int b) {
  if (!b) {
    return make_tuple(a, 1, 0);
  }
  int d, x, y, c;
  c = a / b;
  tie(d, x, y) = euclid(b, a - c * b);
  return make_tuple(d, y, x - c * y);
}

int main() {
  ifstream cin("euclid3.in");
  ofstream cout("euclid3.out");
  int t, a, b, c, d, x, y;
  cin >> t;
  while (t--) {
    cin >> a >> b >> c;
    tie(d, x, y) = euclid(a, b);
    if (c % d == 0) {
      cout << x * (c / d) << " " << y * (c / d) << "\n";
    } else {
      cout << "0 0\n";
    }
  } 
}