Cod sursa(job #3297477)

Utilizator Arhiva_Educationala_2Arhiva Educationala doi Arhiva_Educationala_2 Data 22 mai 2025 17:59:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <bits/stdc++.h>

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

  int rest = a % b, cat = a / b;
  int ret = euclid( b, rest, x, y );
  // a = cat * b + rest
  // b * x + rest * y = 1
  // b * x + (a - cat * b) * y = 1
  // b * x - cat * b * y + a * y = 1
  // b(x - cat * y) + a(y) = 1
  int xx = y;
  int yy = x - cat * y;
  x = xx;
  y = yy;

  return ret;
}

int main() {
  FILE *fin = fopen( "euclid3.in", "r" );
  FILE *fout = fopen( "euclid3.out", "w" );

  int t;
  for( fscanf( fin, "%d", &t ); t--; ){
    int a, b, c;
    fscanf( fin, "%d%d%d", &a, &b, &c );

    if( a == 0 && b == 0 ){
      fprintf( fout, "0 0\n" );
      continue;
    }

    // nu stiu de ce am facut asta...
    int x, y;
    int gcd = euclid( a, b, x, y );
    if( c % gcd != 0 ){
      fprintf( fout, "0 0\n" );
      continue;
    }

    fprintf( fout, "%d %d\n", x * (c / gcd), y * (c / gcd) );
  }

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