編程之美：不要被階乘嚇倒

問題1描述：

給定整數N，N求N！末尾有幾個0。例如N=10，N！=3628800，N！末尾有兩個0

分析：

一、將N！分解質因數，N！=(2^x)*(3^y)*(5^z)......，由於10=2*5，所以問題也就是求M=min(x,z)，容易看出x大於等於z，所以也就是求z

#include 
 
int main(){  
    int N=10;
	int ret=0;
	for(int i=1;i<=N;i++){
		int j=i;
		while(j%5==0){
			ret++;
			j/=5;
		}
	}
	printf("%d\n",ret);
    return 0;  
}  

#include 
 
int main(){  
    int N=10;
	int ret=0;
	while(N){
		ret+=N/5;
		N/=5;
	}
	printf("%d\n",ret);
    return 0;  
}  

問題2描述：

求N！的二進制表示中最低位1的位置

分析：

問題2與問題1的區別只是進制上的不同，對於問題1，答案其實就是N！含有多少個10，那麼對於問題2答案就是N！含有多少個2了。

一、利用公式：N/2+N/4+N/16+......

#include 
 
int main(){  
    int N=10;
	int ret=0;
	while(N){
		N>>=1;
		ret+=N;
	}
	printf("%d\n",ret);
    return 0;  
}  

即：1101+110+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的個數)

#include 
 
int main(){  
    int N=10;
	int ret=0,t=N;
	while(t){
		t&=(t-1);
		ret++;
	}
	printf("%d\n",N-ret);
    return 0;  
}