1.问题描述

1).给定一个整数N，那么N的阶乘N!末尾有多少个0？例如：N=0，N!=3628800，N!的末尾有两个0.

2).求N!的二进制表示中最低1的位置

 

2.分析与解法

首先考虑，如果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，因为在N!分解的数种明显2出现的频率要高于5，所以把公式简化为M=Z。

根据上面的分析，有

 

对于问题1

解法一：要计算Z，最直接的方法，就是计算i（i =1, 2, …, N）的因式分解中5的指数，然后求和：

int lowNumzero1(int n){    int i, j, ret = 0;        for(i = 1; i <= n; i++)    {          j = i;          while(j % 5 ==0)          {                  ret++;                  j /= 5;          }    }        return ret;}

 

 

解法二：公式：Z = [N/5] +[N/5²] +[N/5³] + …（不用担心这会是一个无穷的运算，因为总存在一个K，使得5^K > N，[N/5^K]=0。）公式中，[N/5]表示不大于N的数中5的倍数贡献一个5，[N/5²]表示不大于N的数中5²的倍数再贡献一个5，……代码如下：

int lowNumzero2(int n){    int ret = 0;        while(n)    {           ret += n / 5;           n /= 5;    }        return ret;}

 

 

对于问题2

问题实际上等同于求N！含有质因数2的个数。即答案等于N！含有质因数2的个数加1。

解法一：由于N！中还有质因数2的个数，等于Z = [N/2] +[N/2²] +[N/2³] + …，所有有代码

int lowestOne(int n){    int ret = 0;        while(n)    {           n >>= 1;           ret += n;    }    return ret;}

 

 

解法二：

N！含有质因数2的个数，还等于N减去N的二进制表示中1的数目。