Hiểu bài toán

Cho một số nguyên dương N. Xét tích T = 1 × 2 × 3 × ... × N (tức là N!). Yêu cầu tìm số mũ k lớn nhất sao cho 2^k chia hết T. Nói cách khác, tìm số mũ của thừa số 2 trong phân tích thừa số nguyên tố của N!.

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

Cách Phương pháp chia đôi lặp (Iterative Division)

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long cnt = 0;
    while (n > 1) {
        cnt += n / 2;
        n /= 2;
    }
    cout << cnt;
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Đây là cách tiếp cận dựa trên suy nghĩ: Số lượng số chia hết cho 2 trong dãy 1..N là N/2. Số lượng số chia hết cho 4 là N/4, nhưng những số này đã được tính 1 lần khi chia cho 2, nên ta cần cộng thêm N/4. Tương tự cho 8, 16... Vòng lặp 'while' thực hiện việc này: biến n ban đầu là N, sau mỗi bước ta cập nhật n = n / 2 để tính số lượng số chia hết cho các lũy thừa cao hơn của 2. Ví dụ: Với N=6, vòng lặp chạy:

1. cnt += 6/2 = 3 (số chia hết cho 2: 2, 4, 6)
2. n = 6/2 = 3. cnt += 3/2 = 1 (số chia hết cho 4: 4). Tổng cnt = 4.
3. n = 3/2 = 1. Vòng lặp kết thúc. Đáp án là 4.

Cách Phương pháp lũy thừa 2 (Lũy thừa)

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long ans = 0;
    for (long long i = 2; i <= n; i = i * 2) {
        ans += n / i;
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Đây là cách hiện thực trực tiếp nhất của công thức Legendre: k = N/2 + N/4 + N/8 + .... Vòng lặp for tạo ra các lũy thừa của 2 (i = 2, 4, 8, ...) và cộng dồn kết quả n / i vào biến ans. Vòng lặp dừng lại khi i > n. Độ phức tạp thời gian là O(log N) vì i tăng gấp đôi sau mỗi bước.

Cách Phương pháp Legendre (Công thức trực tiếp)

#include <iostream>

int main() {
    long long N;
    std::cin >> N;
    long long k = 0;
    long long power_of_2 = 2;
    while (power_of_2 <= N) {
        k += N / power_of_2;
        if (power_of_2 > N / 2) {
            break;
        }
        power_of_2 *= 2;
    }
    std::cout << k;
    return 0;
}

• Time Complexity: O(log N)
• Space Complexity: O(1)

Đây là một biến thể của phương pháp lũy thừa 2, sử dụng biến power_of_2 để lưu lũy thừa hiện tại. Điều kiện if (power_of_2 > N / 2) được thêm vào để phòng ngừa tràn số (overflow) cho biến power_of_2 trước khi nhân đôi trong bước tiếp theo, đảm bảo vòng lặp kết thúc đúng cách ngay cả khi power_of_2 sắp vượt quá giới hạn của kiểu dữ liệu long long. Logic tính toán hoàn toàn tương đương với các phương pháp trên.

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

Bài học kinh nghiệm

• Vấn đề yêu cầu tìm số mũ của 2 trong N!, tức là tổng số lượng thừa số 2 trong các thừa số từ 1 đến N.
• Công thức Legendre: Số mũ k bằng tổng các thương số nguyên floor(N / 2^i) với i chạy từ 1 đến vô cùng.
• Một cách hiểu trực quan: Ban đầu có N/2 số chia hết cho 2. Trong số các số còn lại, có N/4 số chia hết cho 4 (tức chứa thêm 1 thừa số 2), có N/8 số chia hết cho 8... Tổng hợp lại chính là công thức trên.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu nhỏ (như int) cho N, dẫn đến tràn số khi tính toán với N lên tới 10^8. Nên dùng long long.
• Làm tròn sai trong phép chia: Phải dùng phép chia lấy nguyên (integer division).
• Sử dụng hàm log hoặc các phép tính lũy thừa thực số (floating point) có thể dẫn đến sai số làm tròn và sai kết quả.