POJ 1423 Big Number：階乘位數的兩種高效計算法

題目

給定整數 m (1 ≤ m ≤ 10^7)，求 m! 的十進制位數。多測試用例，首行給出測試數 n。

數學基礎

log10(m!) = log10(1) + log10(2) + ... + log10(m)，位數 = floor(log10(m!)) + 1。

方法一：預計算前綴和 (空間換時間)

預先計算 a[i] = a[i-1] + log10(i) 至足夠大的 N (如 8,000,000)。查詢時：

• m < N：直接 floor(a[m]) + 1
• m ≥ N：a[N-1] + Σ_{i=N}^m log10(i) 現算補上

#define N 8000000
double a[N];
void init() {
    a[0] = 0;
    for (int i = 1; i < N; ++i) a[i] = a[i-1] + log10(i);
}
int main() {
    init();
    int T, m; scanf("%d", &T);
    while (T--) {
        scanf("%d", &m);
        if (m < N) printf("%d\n", (int)a[m] + 1);
        else {
            double s = a[N-1];
            for (int i = N; i <= m; ++i) s += log10(i);
            printf("%d\n", (int)ceil(s));
        }
    }
}

方法二：斯特靈公式近似 (O(1) 查詢)

n! ≈ √(2πn) (n/e)^n，取對數：

log10(n!) ≈ 0.5*log10(2πn) + n*log10(n/e)

忽略高階小項，直接計算並取 ceil。特判 n=1 為 1 位。

int main() {
    const double pi = acos(-1), e = exp(1);
    int T, n; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        double s = 0.5*log10(2*pi*n) + n*log10(n/e);
        if (n == 1) s = 1;
        printf("%d\n", (int)ceil(s));
    }
}

比較與選擇

競賽中通常採用斯特靈公式，代碼極短且無記憶體壓力。