Cod sursa(job #3224130)

Utilizator TrifoitaBejenescu-Babusanu Stefan Trifoita Data 14 aprilie 2024 19:47:36
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb

/*
Algoritmul lui Euclid extins

a*x + b*y = cmmdc(a,b);

Identitatea lui Bezout spune ca:
a*x + b*y = d (demonstrat), unde d = cmmdc(a,b)

cmmdc(a, b) = cmmdc(b, a mod b)

b*x0 + (a mod b) * y0 = d (1)
a*x + b*y = d (2)

Fie a = b*q+r. Inlocuim in (1) si (2) si obtinem:

(q*b + r) * x + b * y = d
b * x0 + r * y0 = d

Reformulam in functie de b si r:

(q*x + y) * b + r * x = d
       x0 * b + r * y0 = d

  => x = y0 si x0 = q*x + y <=> y = x0 - q*x, dar x = y0
  <=> y = x0 - q*y0

{
  x = y0
  si
  y = x0 - q * y0
}

*/

#include <bits/stdc++.h>
#define FIN "euclidext.in"
#define FOUT "euclidext.out"

using namespace std;

void extended_euclid(int a, int b, int *d, int *x, int *y) {
  if (b == 0) {
    *d = a;
    *x = 1;
    *y = 0;
  } else {
    int x1, y1;
    extended_euclid(b, a % b, d, &x1, &y1);
    *x = y1;
    *y = x1 - (a/b)*y1;
  }
}

int main() {
  int a, b, c, T;

  freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);

  scanf("%d", &T);

  while(T--) {
    scanf("%d %d %d", &a, &b, &c);
    int d, x, y;

    extended_euclid(a, b, &d, &x, &y);

    if (c%d != 0) printf("%d %d\n", 0, 0);
    else printf("%d %d\n", (c/d*x), (c/d*y));
  }

  return 0;
}