Cod sursa(job #2670974)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 11 noiembrie 2020 08:23:42
Problema Algoritmul lui Euclid extins Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.93 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( long long n, int sep ){
  char str[9 + 2] = "0000000000";
  int i = 9;

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

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

  str[i] = sep;
  while( n > 0 ){
    str[--i] = (n % 10) + '0';
    n /= 10;
  }

  fputs(str + i, fout);
}

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, ' ');
    fputint(y, '\n');
  }

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