P1591 阶乘数码 【高精】

题目描述

求 n!n!n! 中某个数码出现的次数。
输入格式

第一行为 t(t≤10)t(t \leq 10)t(t≤10)，表示数据组数。接下来 ttt 行，每行一个正整数 n(n≤1000)n(n \leq 1000)n(n≤1000) 和数码 aaa。
输出格式

对于每组数据，输出一个整数，表示 n!n!n! 中 aaa 出现的次数。
输入输出样例
输入 #1

2
5 2
7 0

输出 #1

1
2

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 1e5 + 10;
int n, k;

struct bign{
	int len;
	int d[maxn];
	bign() {
		len = 0;
		memset(d, 0, sizeof(d));
	}
};

bign mul(bign a, int b) {
	int carry = 0;
	bign res;
	for(int i = 0; i < a.len; i++) {
		int tem = a.d[i] * b + carry;
		res.d[res.len++] = tem % 10;
		carry = tem / 10;
	}
	while(carry) {
		res.d[res.len++] = carry % 10;
		carry /= 10;
	}
	while(res.len > 1 && res.d[res.len - 1] == 0)	res.len--;
	return res;
}

void solve() {
	cin >> n >> k;
	bign res;
	res.len = 1;
	res.d[0] = 1;
//	res = mul(res, 23);
	for(int i = 1; i <= n; i++) {
		res = mul(res, i); 
	}
	int ans = 0;
	for(int i = 0; i < res.len; i++) {
	//	cout << res.d[i];
		if(res.d[i] == k)
			ans++;
	}
	cout << ans << endl;
}

int main() {
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}