階乘位數計算：對數公式與 C 語言實現

階乘位數計算：對數公式與 C 語言實現

直接計算 N! 會迅速溢出（20! 已超過 64 位整數範圍）。求十進制位數只需利用對數性質，避開大數運算。

數學推導

設 A = N!，十進制位數 d 滿足：

10^(d-1) ≤ A < 10^d
⇒ d-1 ≤ log10(A) < d
⇒ d = floor(log10(A)) + 1

又 log10(N!) = log10(1) + log10(2) + ... + log10(N)，故：

d = floor( Σ_{i=1}^N log10(i) ) + 1

算法複雜度

• 時間：O(N) —— 單次查詢需累加 N 項；
• 空間：O(1) —— 僅需一個 double 累加器；
• 若多次查詢，可預計算前綴和 prefix[i] = Σ_{k=1}^i log10(k)，查詢降為 O(1)。

C 語言參考實現

#include <stdio.h>
#include <math.h>

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

測試樣例

精度與邊界討論

• double 53 位尾數（約 15-16 位十進制有效數字），累加至 N=10^6 時 sum ≈ 5.5e6，相對誤差極小，**不影響整數部分取整**；
• 極大 N（>10^7）可考慮 long double 或 Stirling 公式近似：log10(N!) ≈ N*log10(N/e) + 0.5*log10(2πN)。

延伸：任意進制位數

若求基數 B 下位數，將 log10 替換為 logB（或用換底公式 log10(i)/log10(B)）。

這道題是「數學洞察力」與「工程實現」的完美結合：用對數把乘法變加法，用浮點數避開大整數，幾行代碼解決看似困難的問題。