不要被阶乘吓倒

题目一

求N!的末尾有多少个0?

N!=1*2*3*...*(N-1)*N;


      10的质数分解只有2和5,那么假设N!中通过质数分解,所能得到的2的个数为X,所能得到的5的个数为Y,则X和Y中较小的一个极为连乘中10的个数,也就得到了N!结果中末尾的0的个数。不难看出,X > Y在N!中是一定成立的,则问题转化为求Y。

最简单的解法:

int count=0;
for(int i=1;i<=N;i++)
{
       int num=i;
      while(num % 5 == 0)
    {
          count ++;
          num/=5;
       }
}
return count;

 
巧妙地解法,只对N进行操作: 

 Y= [ N/5 ] + [ N/(5^2) ] + [ N/(5^3) ] + ...... 总存在一个K,使得5^K > N,即[N / 5^K] == 0.

公式中,[N / 5]表示不大于N的数中5的倍数的个数,每一个都为  N!贡献了一个质因子5;[N / (5^2) ]表示不大于N的数中5*5的倍数的个数,每一个都又为N!贡献了一个质因子5,依次类推,可得:

int count=0;
      while(N != 0)
    {
          N/=5;
          count+=N;
       }
}
return count;


问题二:

求N!的二进制表示中最低位1的位置。

       由上题可以看出,此题求的是N!中质因子2的个数X。

int count=0;
      while(N != 0)
    {
          N>>=1;
          count+=N;
       }
}
return count;




评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值