解题思路

题目要求计算 n 的阶乘，n 最大 100。100! 有 158 位数字，int 和 long long 都存不下，要用高精度：用数组一位一位地存。

思路：

阶乘就是从 1 乘到 n。用数组存结果的每一位，每次乘一个数时，每一位都乘这个数并处理进位。

步骤：

1. 结果初始为 1，a[1] 存个位
2. 从 1 乘到 n：
   • 每一位 a[j] 都乘 i，再加上进位
   • 新的进位 = a[j] ÷ 10，a[j] 保留个位
   • 如果最高位产生了进位，位数加 1
3. 从最高位到个位逆序输出

举例 5! = 120：

• 1×1=1
• 1×2=2
• 2×3=6
• 6×4=24（个位4，十位2）
• 24×5=120

为什么要高精度？ 因为 100! 太大，普通整数存不下，用数组一位一位存就能算任何大小的数。

参考代码

#include <iostream>
using namespace std;

int a[1005], n, x, len = 1;

int main() {
    cin >> n;
    a[1] = 1;  // 结果初始为 1，a[1] 是个位

    for (int i = 1; i <= n; i++) {  // 从 1 乘到 n
        x = 0;  // 进位
        for (int j = 1; j <= len; j++) {
            a[j] = a[j] * i + x;
            x = a[j] / 10;
            a[j] = a[j] % 10;
            if (x > 0 && j == len) len++;  // 最高位进位
        }
    }

    for (int i = len; i >= 1; i--) cout << a[i];  // 逆序输出
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，n 次乘，每次处理当前位数
• 空间复杂度：O(N)，存每一位数字