求10000以内n的阶乘

题目描述

求 $n!$ 的精确值（约定 $0! = 1$ ），结果不含前导零。

输入：一行一个整数 $n$ （ $0 \leqslant n \leqslant 10000$ ）。

输出：一行，即 $n!$ 的值。

样例输入：4　样例输出：24

思路

$10000!$ 有 35660 位，64 位整数装不下，必须手写高精度：用数组 a 从低位到高位一位存一个十进制数字，a[0] 记位数。从 1 乘到 $n$ ，每次把现有每一位乘 $i$ 再统一进位即可，复杂度 $O(nD)$ （ $D$ 为结果位数）。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 22:02
# update_at: 2026-09-29 22:02

import sys
from math import factorial

MAX_N = 10000
# n! 的位数约为 n·log10(n/e)：10000! 有 35660 位，远超 Python 3.11 起默认的
# int→str 转换上限 4300 位，这里按题面上界放宽到 5·MAX_N 位。
sys.set_int_max_str_digits(5 * MAX_N)


def factorial_digits(n: int) -> str:
    """n! 的十进制字符串；n = 0 时约定 0! = 1。"""
    # Python 的 int 是任意精度，factorial 内部按位打包分治相乘，
    # 乘法的代价按机器字而不是按十进制位计，比逐位手写高精乘快得多。
    return str(factorial(n))


def solve() -> None:
    """读入一个整数 n，输出 n! 的精确值。"""
    (n,) = map(int, sys.stdin.buffer.read().split())
    print(factorial_digits(n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:18
 * update_at: 2026-10-05 04:18
 */

// 高精度阶乘：数组一位存一个十进制数字，每次乘 i 后统一进位。
#include <cstdio>

typedef long long ll;

const int MAXD = 40000; // 10000! 有 35660 位，开 40000 位足够

int a[MAXD]; // a[0] 是当前位数，a[1..a[0]] 从低位到高位存十进制数字
ll n;        // 题目数据用 ll

int main() {
    scanf("%lld", &n);

    a[0] = 1;
    a[1] = 1; // 初始值为 1，n = 0 时结果就是 1
    for (ll i = 2; i <= n; ++i) {
        // 先逐位乘 i，暂不处理进位
        for (int j = 1; j <= a[0]; ++j)
            a[j] = a[j] * i;
        // 统一进位：超过 10 的部分向高位推进
        for (int j = 1; j <= a[0]; ++j) {
            if (a[j] >= 10) {
                if (j == a[0])
                    a[a[0] + 1] = 0; // 最高位进位时位数加一
                a[j + 1] += a[j] / 10;
                a[j] %= 10;
                if (j == a[0])
                    ++a[0];
            }
        }
    }

    // 从最高位到最低位输出
    for (int j = a[0]; j >= 1; --j)
        printf("%d", a[j]);
    printf("\n");
    return 0;
}

求10000以内n的阶乘

目录

题目描述

思路

参考代码