Cod sursa(job #3210902)

Utilizator LucaSeriSeritan Luca LucaSeri Data 7 martie 2024 17:49:08
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef pair<ll, ll> pll;

int euclid (int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1; y = 0;
    return a;
  }

  int x0, y0;
  int g = euclid(b, a%b, x0, y0);

  x = y0;
  y = x0 - (a/b)*y0;

  return g;
}

int main() {
  #ifdef BLAT
    freopen("stdin", "r", stdin);
    freopen("stderr", "w", stderr);
  #else 
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
  #endif

  cin.tie(0)->sync_with_stdio(0);

  srand(time(NULL));

  int t;
  cin >> t;

  while (t--) {
    int a, b, c;
    cin >> a >> b >> c;

    int x, y;
    int g = euclid(a, b, x, y);

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