NYOJ 84 階乘尾部零的個數 - 質因子分解法

問題描述

給定 n，求 n! 末尾連續 0 的個數。多組測試數據。

數學原理

10 = 2 × 5。階乘中質因子 2 的個數遠多於 5，所以尾部 0 的個數取決於質因子 5 的個數（即 min(cnt2, cnt5) = cnt5）。

cnt5 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

C 代碼實現

#include 

int main() {
    int t, n;
    scanf("%d", &t);
    while (t-- && scanf("%d", &n)) {
        int cnt5 = 0;
        while (n) {
            n /= 5;
            cnt5 += n;
        }
        printf("%d\n", cnt5);
    }
    return 0;
}

複雜度

• 時間：O(log₅ n) 每查詢，極快。
• 空間：O(1)。

注意

原文代碼同時計算了 2 和 5 並取較小值，雖然正確但多此一舉，直接算 5 即可。