在阶乘中查找具有 n 个尾随零的自然数

Question

我需要帮助解决以下问题。

给定一个整数 m，我需要找到正整数的个数 n 和整数，使得 [=12] 的阶乘 =] 以 exactly m zeroes.

结尾

我写了这段代码 工作正常 我得到了正确的输出，但是随着数字的增加它需要 太多时间 .

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 的个数。例如150 由 2*3*5*5 组成，有 1 对 2&5 所以有一个尾随零。每次增加测试数字时，请尝试计算数字中有多少 2 和 5。由此，将以前的结果相加，您可以轻松知道其阶乘包含多少个零。

例如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 
..

参考 Peter de Rivaz 和 Dmitry Bychenko 的评论，他们有一些很好的建议。

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) >= f(x) if a >= 0.

if f(x) = y then x <= y * 5（我们只计算 5 个因素）。

if f(x) = y then x >= y * 4 (这个留给你证明)

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

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

1005、1006、1007、1008、1009 都是这样的数字，它们在阶乘
中恰好有 250 个训练零
编辑如果我（在 2 年后）证明 last，我希望我不会破坏乐趣猜想（见下方评论）：

阶乘内的每个 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.

在阶乘中查找具有 n 个尾随零的自然数

Finding natural numbers having n Trailing Zeroes in Factorial

algorithm

factorial

trailing

python-2.7