Hiểu bài toán

Bài toán yêu cầu tìm số lượng chữ số 0 tận cùng của N! (giá trị giai thừa của N). Số lượng chữ số 0 tận cùng của một số trong hệ thập phân được xác định bởi số lượng cặp thừa số (2, 5) trong phân tích thừa số nguyên tố của số đó. Trong N!, thừa số 2 luôn dồi dào hơn thừa số 5, nên số lượng chữ số 0 tận cùng bằng chính số lượng thừa số 5 trong N!.

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

Cách Vòng lặp tính toán số mũ 5

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    long long count5 = 0;
    for (long long p = 5; p <= N; p *= 5) {
        count5 += N / p;
    }
    cout << count5;
    return 0;
}

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

Phương pháp này tính tổng số lượng thừa số 5 trong N! bằng cách cộng dồn số lượng bội của 5, 25, 125, ... trong khoảng từ 1 đến N. Vòng lặp chạy với số lần là bậc của 5 lớn nhất không vượt quá N.

Cách Chia đôi liên tục

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;

    long long ans = 0;
    while (N > 0) {
        N /= 5;
        ans += N;
    }

    cout << ans;
    return 0;
}

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

Cách tiếp cận này dựa trên công thức: Số mũ 5 trong N! = floor(N/5) + floor(N/25) + floor(N/125) + ... Thuật toán thực hiện chia đôi N liên tục cho 5 và cộng dồn kết quả vào biến ans cho đến khi N về 0.

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

Bài học kinh nghiệm

• Số lượng chữ số 0 tận cùng của N! bằng số lượng thừa số 5 trong phân tích thừa số nguyên tố của N!.
• Số lượng thừa số 5 có thể tính bằng tổng các thương số N/5 + N/25 + N/125 + ...

Lỗi thường gặp

• Sử dụng biến int hoặc short có thể gây tràn số (overflow) khi N có giá trị lớn (lên tới 10^9). Nên dùng kiểu dữ liệu dài hơn như long long.
• Sai lầm khi đếm số lượng số chia hết cho 5 thay vì đếm tổng số mũ của 5 (ví dụ: 25贡献 2 mũ 5 nhưng nếu chỉ đếm số chia hết cho 5 thì chỉ tính 1).