Cod sursa(job #2670973)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 11 noiembrie 2020 08:17:07
Problema Algoritmul lui Euclid extins Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <stdio.h>
#include <ctype.h>

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch, semn = 1;

  while( !isdigit(ch = fgetc(fin)) && ch != '-' );
  if( ch == '-' ){
    ch = fgetint();
    semn = -1;
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n * semn;
}

static inline void fputint( int n ){
  int p10 = 1000000000;

  if( n == 0 ){
    fputc('0', fout);
    return;
  }

  if( n < 0 ){
    fputc('-', fout);
    n = -n;
  }

  while( p10 > n )
    p10 /= 10;

  while( p10 > 0 ){
    fputc('0' + (n / p10) % 10, fout);
    p10 /= 10;
  }
}

static inline int get_cmmdc( int a, int b ){
  if( b == 0 )
    return a;

  return get_cmmdc(b, a % b);
}

/*
  ax + by = 1 =>
  bkx + by + (a % b)x = 1 =>
  b((a/b) * x + y) + (a % b)x = 1
   \____x0______/           ^y0
*/
// cumva merge sa pun inline la functie recursiva...
static inline void euclid_ext( int a, int b, int *x, int *y ){// ax + by = 1; (a, b) = 1
  int x0, y0;

  if( b == 0 ){// stim ca (a, b) = 1 => a = 1
    *x = 1;// 1 * 1 = 1
    *y = 0;// 0 * 0 = 0
    return;
  }

  euclid_ext(b, a % b, &x0, &y0);

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

static inline void solveEq( int a, int b, int c, int *x, int *y ){
  int cmmdc, x0, y0;

  if( a == 0 && b == 0 ){// nu se poate impartii la cmmdc
    *x = 0;
    *y = 0;
    return;
  }

  cmmdc = get_cmmdc(a, b);
  if( c % cmmdc > 0 ){// cazul imposibil
    *x = 0;
    *y = 0;
    return;
  }

  euclid_ext(a / cmmdc, b / cmmdc, &x0, &y0);// rezolvam a'x0 + b'y0 = 1
  *x = x0 * (c / cmmdc);
  *y = y0 * (c / cmmdc);
}

int main(){
  fin  = fopen("euclid3.in",  "r");
  fout = fopen("euclid3.out", "w");
  
  int t, a, b, c, x, y;

  for( t = fgetint() ; t-- ; ){
    a = fgetint();
    b = fgetint();
    c = fgetint();
    
    solveEq(a, b, c, &x, &y);

    fputint(x);
    fputc(' ', fout);
    fputint(y);
    fputc('\n', fout);
  }

  fclose(fin);
  fclose(fout);
  return 0;
}