求阶乘中具有n个尾随零的自然数

Question

我需要以下问题的帮助。

给定一个整数m，我需要求正整数n和整数的个数，使得n的阶乘以m的零结束。

我写了这段代码，它运行良好，我得到了正确的输出，但随着数字的增加，它花费了太多的时间。

a = input()

while a:
 x = []
 m, n, fact, c, j = input(), 0, 1, 0, 0
 z = 10*m
 t = 10**m

 while z - 1:
  fact = 1
  n = n + 1   

  for i in range(1, n + 1):
     fact = fact * i

  if fact % t == 0 and ((fact / t) % 10) != 0:
     x.append(int(n))
     c = c + 1

  z = z - 1

 for p in range(c):
  print x[p],

 a -= 1
 print c

有人能给我一个更有效的方法来做到这一点吗？目前，一个测试用例需要30秒来询问阶乘中带有250尾随零的数字。

谢谢

Answer 1

关注组成一个数字的2和5的数量。e、 g.150由2*3*5*5组成，有1对2

例如，15=15*...*5*4*3*2*1，从2开始：

Number   2s  5s  trailing zeros of factorial
2        1   0   0
3        1   0   0
4        2   0   0
5        2   1   1
6        3   1   1
...
10       5   2   2
...
15       7   3   3
..
24      12   6   6
25      12   8   8   <- 25 counts for two 5-s: 25 == 5 * 5 == 5**2
26      13   8   8 
..   

参考彼得·德·里瓦斯和德米特里·拜琴科的评论，他们得到了一些好的建议。

Answer 2

获取n！的尾随零数 您可以高效地

def zeroes(value):
    result = 0;

    d = 5;

    while (d <= value): 
        result += value // d; # integer division
        d *= 5;

    return result; 

...

# 305: 1234! has exactly 305 trailing zeroes 
print zeroes(1234) 

为了解决这个问题（在n！中n尾随零的数字），您可以使用以下事实：

• 零的数量是单调函数：f（x a）

然后实现二进制搜索（在单调函数上）。

例如，在2500的情况下，我们有测试[4*250..5*250 ] == [1000...1250]的初始范围。二进制搜索将范围缩小为[1005...1009]。

1005、1006、1007、1008、1009都是数字，它们在阶乘中正好有250个训练零

编辑如果我（2年后）证明了最后一个猜测，我希望我不会破坏乐趣（见下面的评论）：

阶乘中的每个5**n乘以2**n产生10**n，因此n零；这就是为什么f（x）是

f(x) = [x / 5] + [x / 25] + [x / 125] + ... + [x / 5**n] + ...

其中，[…]表示地板或整数部分（例如，[3.1415926]==3）。让我们执行简单的操作：

f(x) = [x / 5] + [x / 25] + [x / 125] + ... + [x / 5**n] + ... <= # removing [...]
        x / 5  +  x / 25  +  x / 125  + ... +  x / 5**n  + ... =
        x * (1/5 + 1/25 + 1/125 + ... + 1/5**n + ...) =
        x * (1/5 * 1/(1 - 1/5)) =
        x * 1/5 * 5/4 =
        x / 4

目前为止还不错

 f(x) <= x / 4 

或者如果y=f（x）