阶乘数码

GitHub跳转原题关系图返回列表

预处理到最大 n 的阶乘，用 Python 大整数转字符串后统计指定数字出现次数。

OJ: luogu

题目 ID: P1591

难度:入门

标签:高精度字符串python

日期: 2026-07-15 22:10

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

多组询问，每组给出 n 和一个数码 a，求 n! 的十进制表示中 a 出现了多少次。

思路

n <= 1000，Python 的大整数可以直接保存 1000!。为了避免每组询问都重新算阶乘，先找到所有询问中的最大 n，预处理：

python
factorials[i] = factorials[i-1] * i

回答时把 factorials[n] 转成字符串，用 count(digit) 统计。

这题是 Python 大整数和字符串统计练习，不创建 brute.py。

Python 知识

  • /home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：Python int 支持任意精度整数。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：多组输入可以用 sys.stdin.read().split() 统一读取。
  • str(big_number).count(digit) 可以统计字符出现次数。

代码

python
import sys


data = sys.stdin.read().split()
test_count = int(data[0])
queries = []
max_n = 0

index = 1
for _ in range(test_count):
    n = int(data[index])
    digit = data[index + 1]
    queries.append((n, digit))
    max_n = max(max_n, n)
    index += 2

factorials = [1] * (max_n + 1)
for number in range(1, max_n + 1):
    factorials[number] = factorials[number - 1] * number

answers = []
for n, digit in queries:
    answers.append(str(str(factorials[n]).count(digit)))

print("\n".join(answers))
cpp
/**
 * 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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXLEN = 3000; // 1000! 大约 2568 位

// 大整数乘法：a[0..len_a-1] *= b，b 是一个小整数
// a 是逆序存储的数组，低位在前
int mul_int(int *a, int len_a, int b) {
    int carry = 0;
    for (int i = 0; i < len_a; i++) {
        int prod = a[i] * b + carry;
        a[i] = prod % 10;
        carry = prod / 10;
    }
    while (carry) {
        a[len_a++] = carry % 10;
        carry /= 10;
    }
    return len_a;
}

// 统计大整数 a[0..len-1] 中数码 digit 出现的次数
int count_digit(int *a, int len, int digit) {
    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (a[i] == digit) cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, digit;
        cin >> n >> digit;

        int fact[MAXLEN] = {0};
        fact[0] = 1;      // 0! = 1
        int len = 1;

        // 计算 n!
        for (int i = 2; i <= n; i++) {
            len = mul_int(fact, len, i);
        }

        cout << count_digit(fact, len, digit) << "\n";
    }

    return 0;
}

复杂度

预处理到最大 n 需要做 max_n 次大整数乘法。每组询问需要把对应阶乘转字符串并统计，复杂度与数字位数有关。

总结

Python 处理高精度阶乘题很直接：先用大整数算出结果，再把十进制表示当字符串处理。