P1591 阶乘数码

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

2
5 2
7 0  

输出 #1复制

1
2  

#include<bits/stdc++.h>
using namespace std;
struct bign{
	int d[10000];
	int len;
	bign(){
		len = 0;
		memset(d , 0 , sizeof(d));
	}
};
bign change(int x){
	bign a;
	while(x){
		a.d[a.len++] = x % 10;
		x /= 10;  
	}
	return a;
}
bign multi(bign a , bign b){
	bign c;
	c.len = a.len + b.len;
	for(int i = 0 ; i < a.len ; i++){ 
		for(int j = 0 ; j < b.len ; j++){
			c.d[i + j] += a.d[i] * b.d[j];
			c.d[i + j + 1] += c.d[i + j] / 10;
			c.d[i + j] %= 10;
		}
	} 
	while(c.len - 1 > 0 && c.d[c.len - 1] == 0) c.len--;
	return c;
}
int t , n , a;
int main(){
	scanf("%d" , &t);
	while(t--){
		scanf("%d %d" , &n , &a);
		bign x = change(1);
		for(int i = 2 ; i <= n ; i++){
			x = multi(x , change(i));
		}
		int ans = 0; 
		for(int i = 0 ; i < x.len ; i++){
			if(x.d[i] == a) ans++;
		}
		cout << ans << endl;
	} 
	return 0;
}