Cod sursa(job #2506482)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 8 decembrie 2019 11:37:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>

using namespace std;

void extended_euclid(long long a, long long&x, long long b, long long &y, long long &d)
{ // solves a*x + b*y = gcd(a,b)
  if (b == 0) {
    x = 1;
    y = 0;
    d = a;
    return;
  }
  long long x_, y_;
  extended_euclid(b, x_, a%b, y_, d);
  // we now have b * x_ + (a - [a/b]*b) * y_ = d (1)
  // we want to compute            a*x + b*y = d (2)
  // so in (2) x is a's coefficient and y is b's coefficient from (1)
  x = y_;
  y = x_ - (a/b)*y_;
}


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

  int N;
  long long a,b,c;
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld%lld%lld", &a, &b, &c);
    long long x, y, d;
    extended_euclid(a, x, b, y, d);
    // we now have a*x + b*y = d => multiply by c/d
    if (c % d != 0) {
      printf("0 0\n");
      continue;
    }
    printf("%lld %lld\n", x*c/d, y*c/d); 
  }
  
  return 0;
}