编程之美----不要被阶乘吓到

任一个正整数都能分解成质数的连乘，因此求N！末尾有多少个0，等于质因数分解之后5的个数，而求5的个数可以用如下代码实现：

ret =0; while(N) {ret += N/5;N/=5; } View Code

5的倍数贡献一个5,5的平方的倍数再贡献一个5，如此继续下去。。。。

问题二：求N！的二进制表示中最低位1的位置，等价于求N! 含有质因数2的个数加1，因为如果将N！表示成2的多少次幂乘以一个数，那么就可以表示成2的多少次幂+2的更多的次幂。于是将上面的代码稍微修改就可以用来求此问题，另外N！含有质因数2的个数，还等于N减去N的二进制表示中1的数目。假如N=11011，这些0,1都代表二进制，那么

1101(这里可以理解为N/2)+110(N/4)+11+1

=(1000 +100 +1)

+(100   +10)

+(10     +1)

+1

=(1000 +100+10+1) + (100 +10 +1)+1

=1111+111+1

=（10000-1）+（1000-1）+(10-1)+(1-1)=11011-(N二进制表示中1的个数）。

 

相关题目：

给定整数n，判断它是否为2的方幂。可用（n>0&&((n&(n-1))==0)求解

转载于:https://www.cnblogs.com/wen-ge/p/4082441.html

总结

以上是生活随笔为你收集整理的编程之美----不要被阶乘吓到的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。