同样是<编程之美>中的题目. 解题思路是最低位1的未知等同于N!中质因数2的个数,即答案是N!中含有质因数2的个数+1,然后书上给出这么一个公式(假设N!中质因数2的个数为Z):
Z=[N/2]+[N/4]+[N/8]+[N/16]+...
这个公式怎么证明? 书上给出一个提示([N/k]等于1,2,3,...,N中能被k整除的数的个数).
这个证明其实挺简单的，仔细想想就能明白了。
针对 1..N 范围中的所有整数：
N/(k^1)表示包含因子 k 的整数数量N/(k^2)表示包含因子 k*k 的整数数量。这些所有能被k*k整除的整数相乘会包含2*N/(k^2)个因子k，但因为这些数字也满足条件1，所以在条件1中已经计入一半，这里不需要再重复计入了。N/(k^3)表示包含因子 k*k*k 的整数数量。这些所有能被k*k*k整除的整数相乘会包含3*N/(k^3)个因子k，但是1/3在条件1中计入，1/3在条件2中计入，因此这里也只需要计入一次。
你看，上面三个加起来，就等于在 1..N 中所有能被 k、k^2、k^3 整除的整数之积包含的因子k的个数。继续推广开来，找到一个 m ，使得 N < k^m ，那么 Z = sum(N/(k^i)) (1<=i<m) 就是 1..N 中所有数字的积(也就是N!)中包含因子k的个数。
顺便说一下，这个题目有个变种，供扩展思考：N!的十进制表示中末尾有几个零？