Số chữ số 0 ở cuối giai thừa trong C++

Tính số chữ số 0 ở cuối kết quả giai thừa. Ví dụ: 5! = 120 → 1 số 0. 20! = 2432902008176640000 → 4 số 0.

Cách đơn giản: tính giai thừa rồi đếm số 0. Nhưng thất bại với n lớn. Cách tốt hơn: số 0 cuối = số cặp (2,5) trong thừa số nguyên tố. Vì số 2 luôn nhiều hơn số 5, nên chỉ cần đếm số 5.

Công thức: Trailing 0s = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

Thuật toán

1. count = 0
2. for i = 5; n/i ≥ 1; i *= 5: count += n/i
3. return count

Chương trình C++

#include <iostream> 
#include <cmath> 
#define MAX 20 
using namespace std; 

int countTrailingZeros(int n) {
    int count = 0;
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;
    return count;
}

int main() {
    int n = 20;
    cout << "Number of trailing zeros: " << countTrailingZeros(n);
}

Đầu vào/Kết quả

Number of trailing zeroes: 20
Number of trailing zeros: 4

Giải thích

20! có: ⌊20/5⌋=4 (5,10,15,20), ⌊20/25⌋=0 → Tổng = 4 số 0.