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"); 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; }
|