算法刷题【洛谷P1591】阶乘数码
题目描述
求 n! 中某个数码出现的次数。
输入格式
第一行为 t(t≤10)，表示数据组数。接下来 tt 行，每行一个正整数 n(n≤1000) 和数码 a。
输出格式
对于每组数据，输出一个整数，表示 n! 中 a 出现的次数。
输入输出样例
In 1
2
5 2
7 0Out 1
1
2咋一看我好像题都没读懂（可能是我当时智障了吧……）
于是直接看了题解
意思很简单，就是n!的各个位置上a出现的次数
然后看完题解意外得知了要高精*单精
本着我命由我不由天的原则还是long long试了一下……
嗯
好吧
我们来说说高精度……
由于当时老师教高精度的那节课刚好缺课
加上洛谷高精度乘法这道题用python水过的
我只好凭我优秀的抄题解能力自研能力完成这个简单的高精乘
#include <bits/stdc++.h>
using namespace std;
short num[1000001];
int main() {
int tt, n, a, len = 1, jw, cnt;
long long ans;
cin >> tt;
while (tt--) {
memset(num, 0, sizeof(num));
num[0] = 1;
cin >> n >> a;
for (int j = 2; j <= n; j++) {
jw = 0;
for (int i = 0; i < len; i++) {
num[i] = num[i] * j + jw;
jw = num[i] / 10;
num[i] %= 10;
}
while (jw) {
num[len++] = jw % 10;
jw /= 10;
}
}
cnt = 0;
for (int i = 0; i < len; i++)
if (num[i] == a) cnt++;
cout << cnt << endl;
}
}于是得到了这张图
只有70？
而且这道题不给样例下载？？
好吧其实幸亏他没给，不然我研究半天样例也搞不定
只好再去和刚刚参考过的题解比对了一下
第17行少了len = 1;
对就是这一点……
每次没有重新给数组长度赋值
而由于每次有memset，所以数组长度过大没清零只影响数字0数量的统计，所以有70分
不过这再一次告诉了我们赛场上编数据的重要性
AC代码
#include <bits/stdc++.h>
using namespace std;
short num[1000001];
int main() {
int tt, n, a, len = 1, jw, cnt;
long long ans;
cin >> tt;
while (tt--) {
memset(num, 0, sizeof(num));
num[0] = 1;
len = 1; // ！
cin >> n >> a;
for (int j = 2; j <= n; j++) {
jw = 0;
for (int i = 0; i < len; i++) {
num[i] = num[i] * j + jw;
jw = num[i] / 10;
num[i] %= 10;
}
while (jw) { // 加法这里可以用if，乘法进位可能很多必须while
num[len++] = jw % 10;
jw /= 10;
}
}
cnt = 0;
for (int i = 0; i < len; i++)
if (num[i] == a) cnt++;
cout << cnt << endl;
}
return 0;
}