問題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
#includeint 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; }
#includeint 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+......
#includeint 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的個數)
#includeint main(){ int N=10; int ret=0,t=N; while(t){ t&=(t-1); ret++; } printf("%d\n",N-ret); return 0; }