Chương trình C ++ để triển khai thuật toán Euclid mở rộng

Thuật toán Euclid mở rộng chỉ là một cách khác để tính GCD của hai số. Nó có các biến phụ để tính ax + by =gcd (a, b). Sẽ hiệu quả hơn khi sử dụng trong chương trình máy tính

Thuật toán

Begin
   Declare variable a, b, x and y
   gcdExtended(int a, int b, int *x, int *y)
   if (a == 0)
      *x = 0;
      *y = 1;
   return b;
   Take two variables to store the result
   Update x and y using results of recursive call
End

Mã mẫu

#include <bits/stdc++.h>
using namespace std;
int gcdExtended(int a, int b, int *x, int *y) {
   if (a == 0) {
      *x = 0;
      *y = 1;
      return b;
   }
   int x1, y1;
   int gcd = gcdExtended(b%a, a, &x1, &y1);
   *x = y1 - (b/a) * x1;
   *y = x1;
   return gcd;
}
int main() {
   int x, y;
   int a = 35, b = 15;
   cout<<"gcd "<<gcdExtended(a, b, &x, &y);
   return 0;
}

Đầu ra

gcd 5