前一段時間看到一個往年程序競賽的題解, 有一個題目說的是求 100 的階乘末尾有多少個 0. 題解中給出的講解提到, 一個數(shù) n 的階乘末尾有多少個 0 取決于從 1 到 n 的各個數(shù)的因子中 2 和 5 的個數(shù), 而 2 的個數(shù)是遠(yuǎn)遠(yuǎn)多余 5 的個數(shù)的, 因此求出 5 的個數(shù)即可. 題解中給出的求解因子 5 的個數(shù)的方法是用 n 不斷除以 5, 直到結(jié)果為 0, 然后把中間得到的結(jié)果累加. 例如, 100/5 = 20, 20/5 = 4, 4/5 = 0, 則 1 到 100 中因子 5 的個數(shù)為 (20 + 4 + 0) = 24 個, 即 100 的階乘末尾有 24 個 0. 其實不斷除以 5, 是因為每間隔 5 個數(shù)有一個數(shù)可以被 5 整除, 然后在這些可被 5 整除的數(shù)中, 每間隔 5 個數(shù)又有一個可以被 25 整除, 故要再除一次, ... 直到結(jié)果為 0, 表示沒有能繼續(xù)被 5 整除的數(shù)了.

今天無 意間看到有人問 1000 的階乘有幾位數(shù), 上來就用上面的方法算了一下, 249, 又讀一遍題目, 才發(fā)現(xiàn)是求所有的位數(shù), 想了好久也沒有思路, 無奈用 Python 算了一把, 結(jié)果有 2568 位, 可是依然不知道如何計算 1000 階乘的位數(shù), 還好通過結(jié)果驗證了末尾有 249 個 0 是正確的...