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

Question

同样是<编程之美>中的题目. 解题思路是最低位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整除的数的个数).

Answer 1

这个证明其实挺简单的，仔细想想就能明白了。

针对 1..N 范围中的所有整数：

1. N/(k^1) 表示包含因子 k 的整数数量
2. N/(k^2) 表示包含因子 k*k 的整数数量。这些所有能被k*k整除的整数相乘会包含 2*N/(k^2) 个因子k，但因为这些数字也满足条件1，所以在条件1中已经计入一半，这里不需要再重复计入了。
3. 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!的十进制表示中末尾有几个零？