HDU 1042 - N! 高精度階乘計算

問題描述

計算 N! (N ≤ 10000) 的精確值並輸出。結果位數極大，需用高精度（大整數）模擬乘法。

演算法思路

用整數陣列每位儲存一位十進制數字（低位在前）。從 1 乘到 N，每次乘法逐位處理進位。最後從最高非零位向低位輸出。

關鍵點

• 陣列大小預估：10000! 約 35660 位，開 100000 足夠。
• 乘法核心：temp = a[j] * i + carry; a[j] = temp % 10; carry = temp / 10;
• 進位處理：乘法結束後將剩餘 carry 逐位展開存入陣列。
• 輸出時跳過前導零。

完整代碼

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_DIGITS = 100000;
int digits[MAX_DIGITS];

int main() {
    int n;
    while (cin >> n) {
        memset(digits, 0, sizeof(digits));
        digits[0] = 1;
        int len = 1; // 當前有效位數

        for (int i = 2; i <= n; i++) {
            int carry = 0;
            for (int j = 0; j < len; j++) {
                int temp = digits[j] * i + carry;
                digits[j] = temp % 10;
                carry = temp / 10;
            }
            while (carry) {
                digits[len++] = carry % 10;
                carry /= 10;
            }
        }

        // 輸出：從最高位到最低位
        for (int i = len - 1; i >= 0; i--)
            cout << digits[i];
        cout << endl;
    }
    return 0;
}

複雜度

時間 O(N * D) ，D 為位數上限；空間 O(D)。對於 N=10000 完全可行。