Cod sursa(job #2240107)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 12 septembrie 2018 16:36:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <stdio.h>

using namespace std;

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

int main() {
  FILE *fin, *fout ;
  fin = fopen ("euclid3.in", "r" ) ;
  fout = fopen ("euclid3.out", "w" ) ;
  int a, b, n, i, c ;
  fscanf (fin, "%d", &n ) ;
  for (i = 0 ; i < n ; i++ ) {
    int x, y, d ;
    fscanf (fin, "%d%d%d", &a, &b, &c ) ;
    d = gcdext (a, b, x, y ) ;
    if (c % d == 0 )
      fprintf (fout, "%d %d\n", x*(c/d), y*(c/d) ) ;
    else
      fprintf (fout, "0 0\n" ) ;
  }
  return 0;
}