Przejdź do treści

Rozszerzony algorytm Euklidesa

Opis problemu

Implementacja

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>

using namespace std;

int extendedGCD(int a, int b, int &x, int &y) {
  int tmp, quotient, oldX = 1, rest = b, oldRest = a, oldY = 0;
  x = 0;
  y = 1;
  while (rest != 0) {
    quotient = oldRest / rest;

    tmp = rest;
    rest = oldRest - quotient * tmp;
    oldRest = tmp;

    tmp = x;
    x = oldX - quotient * tmp;
    oldX = tmp;

    tmp = y;
    y = oldY - quotient * tmp;
    oldY = tmp;
  }

  y = oldY;
  x = oldX;

  return oldRest;
}

int main() {
  int a = 6;
  int b = 21;
  int x, y, result;

  result = extendedGCD(a, b, x, y);

  cout << a << " * " << x << " + " << b << " * " << y << " = " << result
       << endl;

  return 0;
}