題目描述:計算 n! 的末尾零的個數。
解題思路:末尾零由因子 10 = 2 × 5 產生。n! 中 2 的因子遠多於 5 的因子,因此答案等於 n! 中 5 的因子個數。計算方法:⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...(因為 25 = 5² 貢獻兩個 5,125 = 5³ 貢獻三個 5,以此類推)。
時間複雜度:O(log₅ n) — 每次除以 5,最多 log₅(n) 次迭代。
空間複雜度:O(1) — 只用一個計數變數。
1. count = 0 2. While n >= 5: a. n = n / 5 b. count += n 3. Return count
逐一計算 O(n log n):對每個數從 1 到 n 計算其中 5 的因子個數,累加 — 在 n 很大時過慢且可能溢位。
完整質因數分解:計算 n! 中每個質因數的次數,找最小的 min(2 的次數, 5 的次數) — 正確但不必要複雜。