Cod sursa(job #2572948)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 5 martie 2020 15:04:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

void euclid(int a, int b, int *x, int *y, int *d) {
  if (b == 0) {
    *d = a;
    *x = 1;
    *y = 0;
    return ;
  }
  euclid(b, a % b, x, y, d);
  int c = a / b;
  int x0 = *y;
  int y0 = *x - *y * c;
  *x = x0;
  *y = y0;
}

void solve() {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  int x, y, d;
  euclid(a, b, &x, &y, &d);
  if (c % d != 0)
    printf("0 0\n");
  else
    printf("%d %d\n", 1LL * x * c / d, 1LL * y * c / d);
}

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

  int t;
  scanf("%d", &t);
  while (t--)
    solve();

  return 0;
}