求一個(gè)數(shù)階乘末尾0的個(gè)數(shù)

#include<iostream>
using namespace std;
//給定一個(gè)整數(shù)N,那么N的階乘末尾有幾個(gè)0？N=10,N!=3628800,末尾有2個(gè)0
//1.如果我們從“哪些數(shù)相乘能得到 10”這個(gè)角度來考慮，問題就變得簡單了。
//首先考慮，如果 N！= K×10M，且 K 不能被 10 整除，那么 N！末尾有 M 個(gè) 0。再考慮
//對(duì) N！進(jìn)行質(zhì)因數(shù)分解，N！=（2x）×（3y）×（5z）…，由于 10 = 2×5，所以 M 只跟 X 和 Z
//相關(guān)，每一對(duì) 2 和 5 相乘可以得到一個(gè) 10，于是 M = min（X, Z）。不難看出 X 大于等于 Z，
//因?yàn)槟鼙?nbsp;2 整除的數(shù)出現(xiàn)的頻率比能被 5 整除的數(shù)高得多，所以把公式簡化為 M = Z。
//根據(jù)上面的分析，只要計(jì)算出 Z 的值，就可以得到 N！末尾 0 的個(gè)數(shù)。 
//最直接的方法，就是計(jì)算 i（i =1, 2, …, N）的因式分解中 5 的指數(shù)，然后求和
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] + …（不用擔(dān)心這會(huì)是一個(gè)無窮的運(yùn)算，因?yàn)榭偞嬖谝?//個(gè) K，使得 5K > N，[N/5K]=0。）
//公式中，[N/5]表示不大于 N 的數(shù)中 5 的倍數(shù)貢獻(xiàn)一個(gè) 5，[N/52]表示不大于 N 的數(shù)中 52
//的倍數(shù)再貢獻(xiàn)一個(gè) 5
int count2(int n)
{
	int ret=0;
	while(n)
	{
		ret+=n/5;
		n/=5;
	}
	return ret;
}
int main()
{
	cout<<count1(10)<<endl;
	cout<<count2(10)<<endl;
	return 0;
}

#include<iostream>
using namespace std;
//求N!的二進(jìn)制表示中最低位1的位置給定一個(gè)整數(shù) N，求 N！二進(jìn)制表
//示的最低位 1 在第幾位？例如：給定 N = 3，N！= 6，那么 N！的二進(jìn)制表示（1 010）的最低
//位 1 在第二位。 

//思路：判斷最后一個(gè)二進(jìn)制位是否為 0，若為 0，則將此二進(jìn)制數(shù)右移一位，即為商值（為什
//么）；反之，若為 1，則說明這個(gè)二進(jìn)制數(shù)是奇數(shù)，無法被 2 整除（這又是為什么）。
//所以，這個(gè)問題實(shí)際上等同于求 N！含有質(zhì)因數(shù) 2 的個(gè)數(shù)。即答案等于 N！含有質(zhì)因數(shù)
//2 的個(gè)數(shù)加 1 
//由于 N! 中含有質(zhì)因數(shù) 2 的個(gè)數(shù)，等于 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！含有質(zhì)因數(shù) 2 的個(gè)數(shù)，還等于 N 減去 N 的二進(jìn)制表示中 1 的數(shù)目。我們還可以通過
//這個(gè)規(guī)律來求解。
 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<<lowestOne(3)<<endl;
	cout<<lowestOneCount(3)<<endl;
	return 0;
}