HDU 1042 N!：大整數階乘 C++ 實作與除錯心得

題目需求

計算 N!（N ≤ 1000），結果位數極大，需高精度乘法。陣列大小設 50000 足夠容納 1000! 約 2568 位。

結構體與核心邏輯

struct BigNumber {
    int data[50000];
    int len;
    BigNumber() : len(1) { memset(data, 0, sizeof(data)); }
    BigNumber& operator=(const char *str);
    BigNumber operator*(int a);   // 單純乘以 int
    void print();
    void clearLeadZero();
} ans;

乘法運算子（關鍵：分兩階段處理進位）

BigNumber BigNumber::operator*(int a) {
    BigNumber z;
    int carry = 0, i;
    for (i = 0; i < len; ++i) {
        int p = data[i] * a + carry;
        z.data[i] = p % 10;
        carry = p / 10;
    }
    // 處理剩餘進位
    while (carry) {
        z.data[i++] = carry % 10;
        carry /= 10;
    }
    z.len = i;
    z.clearLeadZero();
    return z;
}

⚠️ 若將 while (carry) 合併進 for 迴圈條件，會導致 i 邏輯錯誤，這是原作者踩過的坑。

主程式

int main() {
    int N;
    while (scanf("%d", &N) != EOF) {
        ans = "1";
        for (int i = 2; i <= N; ++i) ans = ans * i;
        ans.print();
    }
    return 0;
}

除錯心得

1. 初始化清零：operator= 中的 memset 不可省略。
2. 進位處理分離：先跑完現有位數，再用 while (carry) 展開高位。
3. 陣列大小：依題目上限預估，留足餘裕。