Cod sursa(job #149174)

Utilizator alecmanAchim Ioan Alexandru alecman Data 5 martie 2008 13:24:33
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<stdio.h>

#define INPUT "euclid3.in"
#define OUTPUT "euclid3.out"

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

int t;

inline void readValues(){fscanf(fin, "%d", &t);}

void solveFunction();

int euclid(int, int, int &, int &);

int main(){
  readValues();
  solveFunction();
  fclose(fin);
  fclose(fout);
  return 0;
}

void solveFunction(){
  int a,b,x,y,c,div;
  for(int i=1;i<=t;++i){
    fscanf(fin, "%d %d %d", &a, &b, &c);
    div=euclid(a,b,x,y);
    if(c%div)
      fprintf(fout, "0 0\n");
    else
      fprintf(fout, "%d %d\n", x*(c/div),y*(c/div));
  }
}

int euclid(int a, int b, int &x, int &y){
  int x0,y0,div;
  if(b==0){
    x=1;
    y=0;
    return a;
  }
  
  div=euclid(b,a%b,x0,y0);

  x=y0;
  y=x0-(a/b)*y0;
  return div;
}