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

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

Thuật toán

Bắt đầu
    Khai báo biến a, b, x và y
    gcdExtended(int a, int b, int *x, int *y)
    Nếu (a == 0)
        *x = 0; *y = 1; Trả về b;
    Lấy hai biến lưu kết quả
    Cập nhật x và y sử dụng kết quả của lời gọi đệ quy
Kết thúc

Mã ví dụ

#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; 
}

Kết quả

GCD: 5