Cod sursa(job #2910948)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 26 iunie 2022 00:54:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>

void euclid(long long A, long long B, long long &X, long long &Y, long long &D) {
  if (B == 0) {
    D = A;
    X = 1;
    Y = 0;
    return;
  }

  long long XX, YY;
  euclid(B, A % B, XX, YY, D);
  // B * XX + (A - [A/B]*B) * YY = D
  // A * X + B * Y = D
  X = YY;
  Y = XX - (A/B) * YY;
}

int main()
{
  freopen("euclid3.in", "r", stdin);
  freopen("euclid3.out", "w", stdout);


  int N;
  long long A, B, C, D, X, Y;
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld%lld%lld", &A, &B, &C);
    euclid(A, B, X, Y, D);
    if (X * C % D == 0 && Y * C % D == 0) {
      printf("%lld %lld\n", X * C / D, Y * C / D);
    }
    else
      printf("0 0\n");
  }
 
  return 0;
}