题目一
求N!的末尾有多少个0?
N!=1*2*3*...*(N-1)*N;
10的质数分解只有2和5,那么假设N!中通过质数分解,所能得到的2的个数为X,所能得到的5的个数为Y,则X和Y中较小的一个极为连乘中10的个数,也就得到了N!结果中末尾的0的个数。不难看出,X > Y在N!中是一定成立的,则问题转化为求Y。
最简单的解法:
int count=0;
for(int i=1;i<=N;i++)
{
int num=i;
while(num % 5 == 0)
{
count ++;
num/=5;
}
}
return count;
巧妙地解法,只对N进行操作:
Y= [ N/5 ] + [ N/(5^2) ] + [ N/(5^3) ] + ...... 总存在一个K,使得5^K > N,即[N / 5^K] == 0.
公式中,[N / 5]表示不大于N的数中5的倍数的个数,每一个都为 N!贡献了一个质因子5;[N / (5^2) ]表示不大于N的数中5*5的倍数的个数,每一个都又为N!贡献了一个质因子5,依次类推,可得:
int count=0;
while(N != 0)
{
N/=5;
count+=N;
}
}
return count;
问题二:
求N!的二进制表示中最低位1的位置。
由上题可以看出,此题求的是N!中质因子2的个数X。
int count=0;
while(N != 0)
{
N>>=1;
count+=N;
}
}
return count;