Cod sursa(job #2741481)

Utilizator euyoTukanul euyo Data 16 aprilie 2021 08:29:25
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin( "euclid3.in" );
ofstream fout( "euclid3.out" );

int euclid( int a, int b ) {
  if ( b == 0 ) {
	return a;
  }
  return euclid( b, a % b );
}
void euclid_ext( int a, int b, int &x, int &y ) {
  int x0, y0;
  if ( b == 0 ) {
    x = 1, y = 0;
	return;
  }
  euclid_ext( b, a % b, x0, y0 );
  x = y0;
  y = x0 - (a / b) * y0;
}

int main() {
  int t, a, b, c, x, y, d;

  fin >> t;
  while ( t-- ) {
	fin >> a >> b >> c;
    d = euclid( a, b );
	if ( c % d == 0 ) {
	  euclid_ext( a, b, x, y );
	  x *= c / d;
	  y *= c / d;
	} else {
	  x = y = 0;
	}
	fout << x << " " << y << "\n"; 
  }
  fin.close();
  fout.close();
  return 0;
}