Cod sursa(job #524382)

Utilizator mih15cMihai Cirlanaru mih15c Data 21 ianuarie 2011 00:16:31
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.77 kb
/**
 * 003 Algoritmul lui Euclid Extins
 * --------------------------------
 * Mihai Cirlanaru
*/

#include <stdio.h>

void gcd (int a, int b, int *d, int *x, int *y) {
  int x0, y0;
  if (b == 0) {
    *d = a;
    *x = 1;
    *y = 0;
  } else {
    gcd(b, a%b, d, &x0, &y0);
    
    *x = y0;
    *y = x0 - (a/b) * y0;
  }
}

int main() {
  int n, a, b, c, d, x, y;
  FILE *f, *g;
  
  f = fopen("euclid3.in", "r");
  g = fopen("euclid3.out", "w");
  
  /* Read number of pairs */
  fscanf(f, "%d", &n);
  
  while (n--) {
    /* Read current pair */
    fscanf(f, "%d %d %d", &a, &b, &c);
    gcd(a, b, &d, &x, &y);
    
    if ((c % d)) {
      fprintf(g, "0 0\n");
    } else {
      fprintf(g, "%d %d\n", x * (c/d), y * (c/d));
    }
  }

  fclose(f);
  fclose(g);
  return 0;
}