题解：洛谷 P1591 阶乘数码

【题目来源】

洛谷：P1591 阶乘数码 - 洛谷 (luogu.com.cn)

【题目描述】

求 \(n!\) 中某个数码出现的次数。

【输入】

第一行为 \(t(t\le 10)\)，表示数据组数。接下来 \(t\) 行，每行一个正整数 \(n(n\le 1000)\) 和数码 \(a\)。

【输出】

对于每组数据，输出一个整数，表示 \(n!\) 中 \(a\) 出现的次数。

【输入样例】

2
5 2
7 0

【输出样例】

1
2

【算法标签】

《洛谷 P1591 阶乘数码》 #数学# #高精度#

【代码详解】

#include <bits/stdc++.h>
using namespace std;int a[10000], ans[10000]; // a数组用于存储阶乘的结果，ans数组用于存储每个测试用例的答案int main()
{int t, n, b; // t表示测试用例的数量，n表示阶乘的上限，b表示要统计的数字cin >> t; // 输入测试用例的数量// 处理每个测试用例for (int k = 1; k <= t; k++) {ans[k] = 0; // 初始化当前测试用例的答案为0cin >> n >> b; // 输入n和bint x, len = 1; // x用于存储进位，len表示当前阶乘结果的位数memset(a, 0, sizeof(a)); // 初始化a数组为0a[1] = 1; // 初始化阶乘结果为1（1! = 1）// 计算n的阶乘for (int i = 1; i <= n; i++) {x = 0; // 初始化进位为0for (int j = 1; j <= len; j++) {a[j] = a[j] * i + x; // 计算当前位的值（乘以i并加上进位）x = a[j] / 10; // 计算新的进位a[j] %= 10; // 取当前位的个位数if (x != 0 && j == len) len++; // 如果最高位有进位，增加位数}}// 统计阶乘结果中数字b出现的次数for (int i = len; i >= 1; i--) if (a[i] == b) ans[k]++; // 如果当前位等于b，答案加1}// 输出每个测试用例的答案for (int i = 1; i <= t; i++) cout << ans[i] << endl;return 0;
}

【运行结果】

2
5 2
7 0
1
2