题目:Factorial
题意:求N!末尾的0 的数量。
思路:10 = 2 * 5;N!中的2 的数量肯定比 5多;只需寻找5 的数量,暴力寻找TLE;
快点的方法:f(N) = N/5 + f(N/5) ;
我们知道,在1->60的数中,以下的数可以被5整除:
5,10,15,20,25,30,35,40,45,50,55,60
共60/5 = 12(个)。
其中,
25,50可以被25整除,即25和50可以贡献两个5的因子。
即其中可以贡献2个5的因子的个数为60/25 = 2(个)。
贡献3个5的因子的没有了,因为60/125 = 0。
所以共有12 + 2 = 14 (个)5的因子。(即1 * 10 + 2 * 2).
#include <cstdio>int m, n,sum5;
int cal(int n){
if(n == ) return ;
sum5 = n/ + cal(n/);
return sum5;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d", &m);
while(m--){
scanf("%d",&n);
sum5 = ;
printf("%d\n",cal(n));
}
return ;
}