algorithm - 在阶乘中查找具有 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

获取 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) >= f(x)如果a >= 0 .
• 如果f(x) = y然后 x <= y * 5 (我们只计算 5 个因素)。
• 如果f(x) = y然后 x >= y * 4 (让我留给你证明)

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

例如如果是 250零我们有初始范围来测试[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] + ...

哪里[...]代表 floor 或 整数部分(例如 [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)然后 x >= 4 * y Q.E.D.