c++中如何实现大数阶乘算法_c++高精度阶乘计算步骤详解【详解】

因为20!已超long long范围，需用vector模拟高精度：每位存0–9、低位在前，乘法时逐位计算并处理进位，输出前倒序遍历。

为什么不能直接用 long long 算阶乘

因为 20! 就已经超过 long long 最大值（约 9.2e18），50! 有 65 位十进制数，必须用数组或字符串模拟每一位的运算。C++ 标准库不提供内置大整数类型（__int128 仅支持有限范围且不可移植），所以得手写高精度乘法。

用 vector 存储各位数字（低位在前）

这是最常用、最易理解的实现方式：每个 vector 元素存一位十进制数字（0–9），索引 0 表示个位，索引 1 表示十位……这样进位处理自然直观。

• 每次乘

  

  一个整数 k，从低位到高位遍历当前结果数组，执行 digit[i] * k + carry
• 新位数 = (digit[i] * k + carry) % 10，进位 = (digit[i] * k + carry) / 10
• 乘完后若还有 carry > 0，需不断 push_back(carry % 10) 并更新 carry /= 10
• 避免前置零：最终输出时倒序遍历，跳过开头的 0（但注意 0! 和 1! 结果是 "1"，不能全跳）

vector factorial(int n) {
    vector res = {1}; // 0! = 1
    for (int k = 2; k <= n; ++k) {
        int carry = 0;
        for (int i = 0; i < res.size(); ++i) {
            int prod = res[i] * k + carry;
            res[i] = prod % 10;
            carry = prod / 10;
        }
        while (carry) {
            res.push_back(carry % 10);
            carry /= 10;
        }
    }
    return res;
}

输出时别忘了反转顺序

vector 存的是「个位在前」，打印必须从最高位（即 res.back()）开始倒着输出，否则得到的是逆序结果。常见错误是直接循环 i = 0 到 size()-1，输出变成 "123" 而不是 "321"（比如 6! = 720，若不反转会输出 "027"）。

• 正确输出方式：for (int i = res.size() - 1; i >= 0; --i) cout
• 如果用 string 存结果，可先构建再 reverse(s.begin(), s.end())，但不如 vector 直接高效
• 注意 n = 0 或 n = 1 时，res 只有一个元素 {1}，倒序输出仍是 "1"

性能和边界要注意这些点

算法时间复杂度约为 O(n × len)，其中 len 是当前结果的位数（增长约 O(n log n)）。对 n ≤ 10000 是可行的；超过这个量级建议改用分治法（如二分递归 + FFT 优化乘法），但日常 OJ 题目用上述方法足够。

• 不要用 vector 试图节省空间——char 溢出风险高（9 * 10000 = 90000，远超 char 范围），int 更安全
• 输入 n = 0 必须特判或确保初始化为 {1}，否则循环不执行，结果为空
• 某些平台 cout 输出大量数字较慢，可改用 printf 或先拼成 string 再一次性输出
• 如果要返回字符串而非 vector，别在每次乘法后都调用 to_string——转换开销大，最后统一转即可

实际写的时候，最容易漏掉的是进位清空逻辑和输出方向。尤其调试时看到一串乱序数字，第一反应该检查是不是忘了倒过来打印。