求一个数阶乘末尾0的个数-创新互联

#include
using namespace std;
//给定一个整数N,那么N的阶乘末尾有几个0？N=10,N!=3628800,末尾有2个0
//1.如果我们从“哪些数相乘能得到 10”这个角度来考虑，问题就变得简单了。
//首先考虑，如果 N！= K×10M，且 K 不能被 10 整除，那么 N！末尾有 M 个 0。再考虑
//对 N！进行质因数分解，N！=（2x）×（3y）×（5z）…，由于 10 = 2×5，所以 M 只跟 X 和 Z
//相关，每一对 2 和 5 相乘可以得到一个 10，于是 M = min（X, Z）。不难看出 X 大于等于 Z，
//因为能被 2 整除的数出现的频率比能被 5 整除的数高得多，所以把公式简化为 M = Z。
//根据上面的分析，只要计算出 Z 的值，就可以得到 N！末尾 0 的个数。 
//最直接的方法，就是计算 i（i =1, 2, …, N）的因式分解中 5 的指数，然后求和
int count1(int n)
{
	int ret=0;
	int j=0;
	for(int i=1;i<=n;++i)
	{
		j=i;
		while(j%5==0)
		{
			++ret;
			j/=5;
		}
	}
	return ret;
}
//2.公式：Z = [N/5] +[N/52] +[N/53] + …（不用担心这会是一个无穷的运算，因为总存在一
//个 K，使得 5K > N，[N/5K]=0。）
//公式中，[N/5]表示不大于 N 的数中 5 的倍数贡献一个 5，[N/52]表示不大于 N 的数中 52
//的倍数再贡献一个 5
int count2(int n)
{
	int ret=0;
	while(n)
	{
		ret+=n/5;
		n/=5;
	}
	return ret;
}
int main()
{
	cout<
#include
using namespace std;
//求N!的二进制表示中最低位1的位置给定一个整数 N，求 N！二进制表
//示的最低位 1 在第几位？例如：给定 N = 3，N！= 6，那么 N！的二进制表示（1 010）的最低
//位 1 在第二位。 

//思路：判断最后一个二进制位是否为 0，若为 0，则将此二进制数右移一位，即为商值（为什
//么）；反之，若为 1，则说明这个二进制数是奇数，无法被 2 整除（这又是为什么）。
//所以，这个问题实际上等同于求 N！含有质因数 2 的个数。即答案等于 N！含有质因数
//2 的个数加 1 
//由于 N! 中含有质因数 2 的个数，等于 N/2 + N/4 + N/8 + N/16 + …1，
int lowestOne(int N)
{
	int Ret = 1;//+最后的1 
	while(N)
	{
		N >>= 1;
		Ret += N;
	}
	return Ret;
}
//N！含有质因数 2 的个数，还等于 N 减去 N 的二进制表示中 1 的数目。我们还可以通过
//这个规律来求解。
 int count3(int v)
 {
 	int num=0;
 	while(v)
 	{
 		v&=(v-1);
 		++num;
	}
	 return num;
} 
int lowestOneCount(int N)
{
	return N-count3(N)+1;
}
int main()
{
	cout<
创新互联专业为企业提供仁和网站建设、仁和做网站、仁和网站设计、仁和网站制作等企业网站建设、网页设计与制作、仁和企业网站模板建站服务，10年仁和做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            分享文章：求一个数阶乘末尾0的个数-创新互联            

            链接URL：http://cqcxhl.com/article/dshees.html