N!含有多少个 2/5质因子

编程之美127页,N!中含有质因数2的个数 = [N/2] + [N/4] + [N/8] + [N/16] + .....

要理解上式,先看

编程之美126页,N!中含有质因数5的个数Z

N!含有多少个 2/5质因子

举例:N = 25
,即1~25

5的倍数(5,10,15,20,25)贡献一个5

25的倍数贡献一个5

虽然25可以贡献两个5,但是已经在5的倍数中贡献一次了,所以这里就统计一次

也就是说,对于每一个5 M,N只统计一次5,虽然它本身有多个5的质因数,但是已经在前面M-1计算过,所以只需统计一次即可

ret = 0;
while(N) //每执行一次迭代,就求出了 有多少个 5^M 贡献5
{
ret += N / 5; //表示 1-N 中能奉献出5的数的个数
N /= 5;
}

同样思路,便可以理解开头的公式了。

上一篇:LA4329 Ping pong 树状数组


下一篇:selenium面试题