Cod sursa(job #1475415)

Utilizator salam1Florin Salam salam1 Data 24 august 2015 05:05:00
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <cstdio>
int tests, a, b, c;

int gcdExtended(int a, int b, long long& x, long long& y) {
  if (b == 0) {
    x = 1; y = 0;
    return a;
  }
  
  long long x1, y1;
  int d = gcdExtended(b, a % b, x1, y1);
  
  x = y1;
  y = -a / b * y1 + x1;
  
  return d;
}

int main() {
  freopen("euclid3.in", "r", stdin);
  freopen("euclid3.out", "w", stdout);
  
  scanf("%d", &tests);
  while (tests--) {
    scanf("%d%d%d", &a, &b, &c);
    long long x, y;
    int d = gcdExtended(a, b, x, y);
      
    if (c % d != 0) {
      printf("0 0\n");
    } else {
      printf("%lld %lld\n", x * c / d, y * c / d);
    }
  }
  return 0;
}