Cod sursa(job #2416131)

Utilizator avtobusAvtobus avtobus Data 26 aprilie 2019 22:32:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;


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

  int x0, y0, d;
  d = ext_gcd(b, a % b, x0, y0);
  x = y0;
  y = x0 - (a / b) * y0;

  return d;
}

int T, A,B,C;

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

  int T;
  cin >> T;
  while (T--) {
    int A, B, C;
    cin >> A >> B >> C;

    int D, X, Y;
    D = ext_gcd(A, B, X, Y);
    if (C % D) {
      cout << 0 << " " << 0 << endl;
    } else {
      cout << X * (C / D) << " " << Y * (C / D) << endl;
    }
  }

  return 0;
}