Cod sursa(job #438521)

Utilizator Smaug-Andrei C. Smaug- Data 10 aprilie 2010 20:47:22
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <cstdio>

int extended_gcd(int a, int b, int *x, int *y){
  
  if(a%b == 0){
    *x = 0;
    *y = 1;

    return b;
  }

  int lcx, lcy, d;
  d = extended_gcd(b, a%b, &lcx, &lcy);
  *x = lcy;
  *y = lcx-lcy*(a/b);
  
  return d;
}

int main(){

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

  int a, b, c, n;

  scanf("%d", &n);
  for(int i = 0; i < n; i++){
    scanf("%d %d %d", &a, &b, &c);

    int x, y, d;
    d = extended_gcd(a, b, &x, &y);

    if(c%d)
      printf("0 0\n");
    else
      printf("%d %d\n", x*(c/d), y*(c/d));

  }
  
  return 0;
}