洛谷P1591阶乘数码

1. 题目描述

详细题目描述见原题地址

2. Notes

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

高精乘单精算法:

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

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

具体可以参见这篇文章

3. 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}