首页 > 代码库 > 编程之美----不要被阶乘吓到
编程之美----不要被阶乘吓到
任一个正整数都能分解成质数的连乘,因此求N!末尾有多少个0,等于质因数分解之后5的个数,而求5的个数可以用如下代码实现:
ret =0;while(N){ ret += N/5; N/=5;}
5的倍数贡献一个5,5的平方的倍数再贡献一个5,如此继续下去。。。。
问题二:求N!的二进制表示中最低位1的位置,等价于求N! 含有质因数2的个数加1,因为如果将N!表示成2的多少次幂乘以一个数,那么就可以表示成2的多少次幂+2的更多的次幂。于是将上面的代码稍微修改就可以用来求此问题,另外N!含有质因数2的个数,还等于N减去N的二进制表示中1的数目。假如N=11011,那么1101+110+11+1=(10000-1)—(1000-1)+(10-1)+(1-1)=11011-(N二进制表示中1的个数)。
相关题目:
给定整数n,判断它是否为2的方幂。可用(n>0&&((n&(n-1))==0)求解
编程之美----不要被阶乘吓到
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。