nyoj 84阶乘后0的个数

描述

计算n!的十进制表示最后有多少个0

输入
第一行输入一个整数N表示测试数据的组数(1<=N<=100)
每组测试数据占一行,都只有一个整数M(0<=M<=10000000)
输出
输出M的阶乘的十进制表示中最后0的个数
比如5!=120则最后的0的个数为1
样例输入
6
3
60
100
1024
23456
8735373
分析: http://www.cnblogs.com/hansongjiang/archive/2014/05/06.html
0来源于2*5,且将N!中分解后,2的个数大于5的个数所有,0的个数就等于N!中银子5的个数。
f(n!)=1*2*3*4*5*6*7*…(2*5)…(3*5)***(4*5) ….(k*5)* … n
      只考虑5的倍数:其他的必然没有5.
       抽取出来:
5*(1*2*3*k*) (其他的数) 现在已经有k个5了,但是K!中可能含有5,公式为
f(n)=k+f(k!) k=n/5;
k<5,时候,没有0,所以f(n!)=0;k<=4;
递归写法就很简单了。
int fun(int n)
{
if(n<=4) return 0;
else return fun(n/5)+n/5;
 
}
仔细分析后,其实最终就是求N!因子5的个数。
private static int fun2(int n) {
// TODO Auto-generated method stub
int count=0;
for(int i=5;i<=n;i=i+5)
{
if(i%5==0)
{
int j=i/5;
count++;
while(j%5==0)
{
count++;
j=j/5; } } }
return count; }
 
 
在nyoj 提交之后发现,递归的效果还不错。
 
 
 
nyoj 84阶乘后0的个数
 
 
 
 
 
 
 
 
 
 
 
 
 
上一篇:CentOS 查看系统 CPU 个数、核心数、线程数


下一篇:未能正确加载 ”Microsoft.VisualStudio.Editor.Implementation.EditorPackate“包错误解决方法