Cod sursa(job #3323262)

Utilizator calinulCalin Cernat calinul Data 17 noiembrie 2025 22:04:38
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

void euclid( long long a, long long b, long long &d, long long &x, long long &y ) {
  if ( b == 0 ) {
    d = a;
    x = 1;
    y = 0;
  } else {
    long long x0, y0;
    euclid( b, a % b, d, x0, y0 );
    x = y0;
    y = x0 - (a / b) * y0;
  }
}

int main() {
  FILE *fin, *fout;
  long long d, x, y;
  int t, a, b, c;

  fin = fopen( "euclid3.in", "r" );
  fout = fopen( "euclid3.out", "w" );
  for ( fscanf( fin, "%d", &t ); t > 0; t-- ) {
    fscanf( fin, "%d%d%d", &a, &b, &c );
    euclid( a, b, d, x, y );

    if ( c % d != 0 ) {
      fprintf( fout, "0 0\n" );
    } else {
      fprintf( fout, "%lld %lld\n", x * (c / d), y * (c / d) );
    }
  }
  fclose( fout );
  fclose( fin );
  return 0;
}