计算n的阶乘末尾有多少个0

计算n的阶乘末尾有多少个0,例如5! = 120 末尾有1个0,10!= 3628800末尾有2个0。

  • 对于一个多因式相乘, 末尾有多少个0, 取决于有多少个10相乘.
  • 10的倍数也可以为结果贡献0, 比如10, 20, 30, 因此可以记为 P = i * 10
  • 10可以因式分解成5 2, 于是 P = i 5 * 2
  • 对于n!, 共有1 2 ... * n

观察如下满足的P值:

1
2
3
4
P:	10	20	30	40	50	...
i:	1	2	3	4	5	...
5i:	5	10	15	20	25	...
2:	2	2	2	2	2	...

对于11!来说, 1 2 ... 5 ... 10 11, 我们可以取出5和10这两个数, 它们各自只要一个2就可以组成10和20, 于是有2个零. 也就是说, 对于n!阶乘来说, 只要看int(n / 5)就可以知道乘积末尾有几个零, 因为对于小因子(这里是2)来说, 阶乘前面很容易获得(从1阶乘到5 * i, 前面至少有i个2的倍数)

  • 还有一个值得注意的是100, 1000这种也是满足P的, 并且, 相比之前, 依次多加一个0: P = i (5 2)^q 可以贡献q个0. 对于这种情况的处理, 可以采用叠加的方式, int(n / 5) 已经为10 i计入一个0了, int(n / 25) 为100 i再计入一个, 依次类推, 就可以完成计数.
  • 此算法T(n) = O(log(n))
1
2
3
4
5
6
7
8
9
10
11
def factorial_tail_zeros(n):
    zeros = 0
    exp = 1
    while 1:
        base = 5 ** exp
        num = n / base
        if num == 0:
            break
        zeros += num
        exp += 1
    return zeros

还可以对while循环的除法做一下优化:

1
2
3
4
5
6
7
8
9
10
def factorial_tail_zeros(n):
    ''' get num of tail zeros of n! '''
    zeros = 0
    dividend = n
    while 1:
        dividend = dividend / 5
        if dividend == 0:
            break
        zeros += dividend
    return zeros
扩展到任意N进制.
  • 套用前面的分析, 我们假设有个熊孩子闲的蛋疼, 用了变态的6进制, P = i 2 3. 因此, 只需考虑最大的因子3, 将上面函数5换成3即可.
  • 对于2进制, 很简单, 最大因子就是2; 那对于16进制来说呢? 我们可以先算出2进制下的0个数, 然后在除以4就行了(16 = 2 ^ 4). 直接用16算反而会出问题, 因为不是质数, 4 * 4 也可以满足.
  • 好了, 对于24进制, P = i 3 (2 2 2) = i 3 8, 取8为因子, 先算出2进制0个数, 最后, 除以3就是24进制下末尾0的个数.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def factorize(n):
    ''' simple facorize function for small integer '''
    factors = []
    num = n
    for i in xrange(2, n / 2 + 1):
        if num % i == 0:
            factors.append(i)
            factors += factorize(num / i)
            break
    if not factors:  # n is prime
        factors.append(n)
    return factors


def factorial_tail_zeros_nbase(n, base=10):
    base_factors = factorize(base)
    factors_map = {}  # {factor: pow} map
    for f in base_factors:
        factors_map[f] = factors_map.get(f, 0) + 1
    # get the biggest factor
    max_factor = max(factors_map.keys(), key=lambda k: factors_map[k] * k)

    # get zeros at max_factor
    zeros = 0
    dividend = n
    while 1:
        dividend = dividend / max_factor
        if dividend == 0:
            break
        zeros += dividend

    # result should divided by pow of max_factor
    return zeros / factors_map[max_factor]

留言