洛谷P1591阶乘数码

1. 题目描述

详细题目描述见原题地址。

2. Notes

求阶乘我们可以采用高精度乘单精度的方法，不必用两个高精度乘的算法，因为哪怕1000!的阶乘已经是一个很大的数了，但是最大也不过是一个很大的数乘以1000，其中一个乘数很小，不必用高精度表示。而且用双高精度表示还会增加程序的运行时间，高精乘和高精加（特别到大数比如1000!的阶乘）真的会增加很多很多时间的消耗*_*。

高精乘单精算法：

设一个大数为a，一个小数为b。用a的每一位与b相乘得到一个积，结果对10取余为当前结果位，剩余的部分（取整所得）往前进位。

需要注意的是，这里每一位的进位最大达到9×b那么大，而不再是普通竖式乘法单位乘单位的进1。

具体可以参见这篇文章。

3. 题解

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t,i,j,k,n,l,carry=0,tmp,num;
	char a;
	cin>>t;
	for(i=0;i<t;i++){
		string fac("1");//默认置1，n为0或1不进循环也能保证结果正确
		num=0;
		cin>>n>>a;
		for(j=2;j<=n;j++){ //求阶乘 
			l=fac.length();
			for(k=0;k<l;k++){ // 让每一个数与之前的积相乘 
				tmp=(int)(fac[k]-'0')*j+carry;
				carry=tmp/10;
				fac[k]=(char)(tmp%10+'0');
			}
			while(carry>0){
				fac+=(char)(carry%10+'0');
				carry/=10;
			}
		}
		for(j=0;j<fac.length();j++){ //统计个数
			if(fac[j]==a){
				num++;
			}
		}
		cout<<num<<endl;
	}
	return 0; 
}