Thuật toán Euclid tìm ước chung lớn nhất (GCD) và bội chung nhỏ nhất (LCM): C++, Python

Ước chung lớn nhất (GCD) và Bội chung nhỏ nhất (LCM) là gì?

Với hai số nguyên không âm a và b (không đồng thời bằng 0):

• Ước chung lớn nhất — ƯCLN (gcd(a, b)): Là số nguyên dương lớn nhất mà cả a và b đều chia hết. Ví dụ: các ước chung của 48 và 18 là {1, 2, 3, 6}, nên gcd(48, 18) = 6. Quy ước gcd(a, 0) = gcd(0, a) = a.
• Bội chung nhỏ nhất — BCNN (lcm(a, b)): Là số nguyên dương nhỏ nhất chia hết cho cả a và b. Ví dụ: lcm(48, 18) = 144.

Nếu duyệt ngược d từ min(a, b) về 1 để tìm số đầu tiên mà cả a và b cùng chia hết, bạn sẽ mất O(min(a, b)) phép chia. Khi a, b ≈ 10¹², vòng lặp này phải chạy hàng nghìn tỷ bước và bị quá thời gian (TLE). Thuật toán Euclid rút ngắn công việc đó xuống chỉ còn vài chục bước.

Ý tưởng trực quan qua bài toán lát gạch hình chữ nhật

Vì sao gcd(a, b) luôn bằng gcd(b, a % b)? Hãy hình dung một căn phòng hình chữ nhật kích thước 48 × 18 mét và bạn muốn lát kín sàn bằng các viên gạch hình vuông cỡ d × d sao cho cạnh d là lớn nhất có thể:

• Để lát kín cạnh ngắn 18 và cạnh dài 48, cạnh viên gạch d phải là ước chung của 48 và 18. Vậy cạnh viên gạch vuông lớn nhất chính là gcd(48, 18).
• Từ hình chữ nhật 48 × 18, ta cắt ra tối đa các hình vuông lớn cỡ 18 × 18. Vì 48 = 18 × 2 + 12, ta cắt được 2 hình vuông 18 × 18 và còn dư một hình chữ nhật nhỏ kích thước 12 × 18 (tức b × (a % b)).
• Nhận xét: Mọi viên gạch vuông d × d lát kín cạnh 18 thì đương nhiên lát kín hai hình vuông 18 × 18 vừa cắt ra. Do đó, viên gạch d × d lát kín căn phòng 48 × 18 khi và chỉ khi nó lát kín phần còn dư 18 × 12.

Lặp lại quy tắc cắt hình vuông theo cạnh ngắn hơn cho tới khi không còn phần dư:

Về mặt đại số, đặt a = b × q + r (với r = a % b). Nếu d là ước chung của a và b thì r = a - b × q cũng chia hết cho d; ngược lại nếu d là ước chung của b và r thì a = b × q + r cũng chia hết cho d. Tập ước chung của (a, b) và (b, r) trùng nhau nên gcd(a, b) = gcd(b, a % b).

Cách tính BCNN (LCM) chống tràn số 64-bit

Giữa ƯCLN và BCNN của hai số nguyên dương a, b luôn có đẳng thức a × b = gcd(a, b) × lcm(a, b). Tuy nhiên, viết lcm = (a * b) / gcd(a, b) rất dễ gây tràn số trong C++:

• Với a = 10¹² và b = 1,5 × 10¹², ta có gcd(a, b) = 5 × 10¹¹ và lcm(a, b) = 3 × 10¹² (nằm gọn trong kiểu long long).
• Nhưng nếu nhân a * b = 1,5 × 10²⁴ trước, tích trung gian vượt quá giới hạn 2⁶³ - 1 ≈ 9,22 × 10¹⁸ của long long và bị tràn số!

Vì a luôn chia hết cho gcd(a, b), quy tắc bắt buộc khi viết hàm lcm là chia trước, nhân sau: lcm(a, b) = (a / gcd(a, b)) * b

Code tìm ƯCLN, BCNN và hàm có sẵn trong C++17, Python

Ngoài việc tự viết vòng lặp while (b != 0), bạn có thể gọi hàm chuẩn có sẵn:

• C++17 trở lên: std::gcd(a, b) và std::lcm(a, b) trong thư viện <numeric>.
• Python 3: math.gcd(a, b) và math.lcm(a, b).

#include <iostream>
#include <numeric>

using namespace std;

// 1. Thuật toán Euclid tìm ƯCLN bằng vòng lặp trong O(log(min(a, b)))
long long gcd_euclid(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 2. Tính BCNN an toàn: chia trước nhân sau để tránh tràn số 64-bit
long long lcm_an_toan(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd_euclid(a, b)) * b;
}

int main() {
    cout << gcd_euclid(48, 18) << " " << lcm_an_toan(48, 18) << "\n";

    // Với a = 10^12, b = 1.5 * 10^12, tích a * b = 1.5 * 10^24 vượt quá long long,
    // nhưng chia trước nhân sau vẫn tính đúng lcm = 3 * 10^12
    long long a = 1000000000000LL, b = 1500000000000LL;
    cout << gcd_euclid(a, b) << " " << lcm_an_toan(a, b) << "\n";

    // Đối chiếu với hàm có sẵn std::gcd và std::lcm trong <numeric> (từ C++17)
    bool khop = (std::gcd(a, b) == gcd_euclid(a, b)) && (std::lcm(a, b) == lcm_an_toan(a, b));
    cout << khop << "\n";
    return 0;
}

import math


def gcd_euclid(a: int, b: int) -> int:
    """Thuật toán Euclid tìm ƯCLN bằng vòng lặp trong O(log(min(a, b)))."""
    while b != 0:
        a, b = b, a % b
    return a


def lcm_an_toan(a: int, b: int) -> int:
    """Tính BCNN bằng phép chia nguyên trước, nhân sau."""
    if a == 0 or b == 0:
        return 0
    return (a // gcd_euclid(a, b)) * b


if __name__ == "__main__":
    print(gcd_euclid(48, 18), lcm_an_toan(48, 18))

    a, b = 1_000_000_000_000, 1_500_000_000_000
    print(gcd_euclid(a, b), lcm_an_toan(a, b))

    # Đối chiếu với hàm có sẵn math.gcd và math.lcm trong Python
    khop = (math.gcd(a, b) == gcd_euclid(a, b)) and (math.lcm(a, b) == lcm_an_toan(a, b))
    print(1 if khop else 0)

Chương trình in ra 6 144, 500000000000 3000000000000 (không tràn số ở 10¹²) và 1 (khớp với thư viện chuẩn).

Vì sao thuật toán Euclid có độ phức tạp O(log(min(a, b)))?

Phép chia lấy dư r = a % b không giảm cố định một nửa ở từng bước đơn lẻ như tìm kiếm nhị phân, nhưng hãy xét 2 bước liên tiếp từ (a, b) sang (b, r) với a ≥ b > 0:

• Nếu b <= a / 2: Ngay sau 1 bước, số chia mới b đã nhỏ hơn hoặc bằng a / 2.
• Nếu b > a / 2: Thương nguyên a / b bằng 1, nên phần dư r = a % b = a - b < a / 2.

Vậy cứ sau 2 bước chia lấy dư, giá trị các số giảm đi ít nhất một nửa, nên số phép chia tối đa không quá 2 × log₂(min(a, b)):

Trường hợp chạy nhiều bước nhất là khi a, b là hai số Fibonacci liên tiếp (do thương luôn bằng 1), nhưng ngay cả khi a, b ≤ 10¹⁸ cũng chỉ tốn tối đa 87 phép chia.

Thuật toán Euclid mở rộng (Extended Euclidean Algorithm)

Theo định lý Bézout, với mọi cặp số nguyên a, b, luôn tồn tại cặp số nguyên (x, y) sao cho a × x + b × y = gcd(a, b). Thuật toán Euclid mở rộng tìm đồng thời cả g = gcd(a, b) lẫn (x, y):

1. Điểm dừng (b == 0): gcd(a, 0) = a, phương trình a × x + 0 × y = a có nghiệm x = 1, y = 0.
2. Bước quy nạp: Giả sử gọi đệ quy cho (b, a % b) trả về (x₁, y₁) thỏa mãn b × x₁ + (a % b) × y₁ = g. Thay a % b = a - (a / b) × b vào và nhóm theo a, b: a × y₁ + b × (x₁ - (a / b) × y₁) = g Suy ra công thức cập nhật ngược từ dưới lên: x = y₁ và y = x₁ - (a / b) × y₁.

Bảng chạy từng bước của ext_gcd(30, 12) cho phương trình 30x + 12y = 6:

Ứng dụng tìm nghịch đảo modulo tổng quát: Để tìm x sao cho (a × x) % m == 1, ta giải a × x + m × y = 1 bằng Euclid mở rộng (khi gcd(a, m) == 1). Khác với định lý Fermat nhỏ dùng lũy thừa nhị phân chỉ chạy được khi m nguyên tố, Euclid mở rộng áp dụng được cho mọi số m bất kỳ nguyên tố cùng nhau với a.

#include <iostream>
#include <tuple>

using namespace std;

// Thuật toán Euclid mở rộng: tìm (g, x, y) sao cho a * x + b * y = g = gcd(a, b)
tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    auto [g, x1, y1] = ext_gcd(b, a % b);
    long long x = y1;
    long long y = x1 - (a / b) * y1;
    return {g, x, y};
}

int main() {
    auto [g1, x1, y1] = ext_gcd(30, 12);
    // 30 * 1 + 12 * (-2) = 6
    cout << g1 << " " << x1 << " " << y1 << "\n";

    auto [g2, x2, y2] = ext_gcd(17, 100);
    // 17 * (-47) + 100 * 8 = 1 -> nghịch đảo modulo 100 của 17 là (-47 % 100 + 100) % 100 = 53
    long long nghich_dao = (x2 % 100 + 100) % 100;
    cout << g2 << " " << x2 << " " << y2 << " " << nghich_dao << "\n";
    return 0;
}

def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Thuật toán Euclid mở rộng: trả về (g, x, y) thỏa a * x + b * y = g = gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y


if __name__ == "__main__":
    g1, x1, y1 = ext_gcd(30, 12)
    print(g1, x1, y1)

    g2, x2, y2 = ext_gcd(17, 100)
    nghich_dao = x2 % 100
    print(g2, x2, y2, nghich_dao)

Chương trình in ra 6 1 -2 (30×1 + 12×(-2) = 6) và 1 -47 8 53 (nghịch đảo của 17 theo modulo 100 là 53, vì 17 × 53 = 901 ≡ 1 (mod 100)).

Lỗi hay gặp

Luyện ngay trên Big-O Coding

Thực hành ngay thuật toán Euclid tìm ƯCLN, BCNN qua các bài tập dưới đây trên Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::gcd, std::lcm
• Python Documentation: math.gcd & math.lcm
• cp-algorithms: Euclidean algorithm for computing the greatest common divisor