求一個數階乘末尾0的個數

#include<iostream>
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<<count1(10)<<endl;
	cout<<count2(10)<<endl;
	return 0;
}

#include<iostream>
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<<lowestOne(3)<<endl;
	cout<<lowestOneCount(3)<<endl;
	return 0;
}