HDU 1018 Big Number 大數階乘位數計算

HDU 1018 Big Number 題目詳解

給定整數 n (1 ≤ n ≤ 10⁷)，求 n! 的十進制位數。直接計算階乘會導致溢出，利用對數性質：log₁₀(n!) = Σ log₁₀(i)，位數 = ⌊log₁₀(n!)⌋ + 1。

數學原理

對於任意正整數 a，其十進制位數等於 ⌊log₁₀(a)⌋ + 1。因為 log₁₀(a×b) = log₁₀(a) + log₁₀(b)，所以 log₁₀(n!) = Σᵢ₌₂ⁿ log₁₀(i)。累加對數值後取整加一即得答案。

C++ 代碼實現

#include <cstdio>
#include <math.h>

int main() {
    int T, i, n;
    double s;
    scanf("%d", &T);
    while (T--) {
        s = 0;
        scanf("%d", &n);
        for (i = 2; i <= n; i++) 
            s += log10(i);
        printf("%d\n", (int)s + 1);
    }
    return 0;
}

樣例測試

輸入：2、10、20 → 輸出：7、19。驗證：10! = 3628800 (7位)，20! = 2432902008176640000 (19位)。

優化提示

• 預計算前綴和可應對多次查詢
• 注意 double 精度在大 n 時的誤差
• 可使用 Kamenetsky 公式 O(1) 近似計算