Hiểu bài toán

Bài toán yêu cầu tìm Bội Chung Nhỏ Nhất (BCNN) của hai số nguyên dương a và b. BCNN của a và b là số nguyên dương nhỏ nhất mà chia hết cho cả a và b. Ví dụ, BCNN của 10 và 12 là 60. Dải đầu vào: 1 ≤ a, b ≤ 10^5.

Các cách tiếp cận

Cách Duyệt qua các bội số lớn nhất

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    long long max_val = max(a, b);
    for (long long i = 1; ; ++i) {
        long long candidate = max_val * i;
        if (candidate % a == 0 && candidate % b == 0) {
            cout << candidate;
            break;
        }
    }
}

• Time Complexity: O(BCNN(a, b) / max(a, b)) - có thể rất lớn nếu BCNN lớn
• Space Complexity: O(1)

Phương pháp này dựa trên định nghĩa BCNN. Nó bắt đầu từ số lớn hơn trong a và b và lặp qua các bội số của nó (maxval * 1, maxval * 2, ...) cho đến khi tìm thấy số đầu tiên chia hết cho cả hai số. Approach này cực kỳ chậm và thường không khả thi trong kỳ thi lập trình nếu a, b có giá trị lớn.

Cách Công thức tính BCNN qua GCD

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    long long a, b;
    cin >> a >> b;
    // Chia a cho GCD trước để tránh tràn số
    long long lcm = (a / gcd(a, b)) * b;
    cout << lcm;
}

• Time Complexity: O(log min(a, b))
• Space Complexity: O(1)

Đây là phương pháp chuẩn và hiệu quả nhất. Nó dựa trên công thức: BCNN(a, b) * GCD(a, b) = a * b. Do đó, BCNN(a, b) = (a * b) / GCD(a, b). Để tránh tràn số (overflow) khi a và b lớn, ta nên tính toán theo thứ tự (a / GCD(a, b)) * b. Hàm GCD có thể tính hiệu quả bằng thuật toán Euclid.

Cách Sử dụng thư viện chuẩn C++ (std::gcd)

#include <iostream>
#include <numeric> // Required for std::gcd in C++17
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    long long g = gcd(a, b); // std::gcd available in C++17
    long long lcm = (a / g) * b;
    cout << lcm;
}

• Time Complexity: O(log min(a, b))
• Space Complexity: O(1)

Đây là cách viết ngắn gọn và hiện đại nhất nếu bạn dùng C++17 trở lên. Nó sử dụng hàm std::gcd có sẵn trong thư viện <numeric> để tính GCD thay vì tự viết hàm, nhưng logic tính BCNN vẫn giữ nguyên là (a / GCD) * b để đảm bảo an toàn số nguyên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Công thức quan trọng: BCNN(a, b) = (a * b) / GCD(a, b).
• Luôn chia một trong hai số cho GCD trước khi nhân với số còn lại để tránh overflow số nguyên (ví dụ: (a / g) * b thay vì (a * b) / g).
• Thuật toán Euclid là cách hiệu quả nhất để tính GCD.

Lỗi thường gặp

• Làm tròn số khi chia nếu dùng số thực (nên dùng số nguyên).
• Tràn số nguyên khi tính a * b nếu a và b lớn (tránh bằng cách chia sớm).
• Quên xử lý trường hợp a hoặc b bằng 0 (trong bài này đề bài giới hạn a, b >= 1 nên không cần, nhưng trong lý thuyết chung cần lưu ý).