在阶乘中找到具有n个尾随零的自然数 [英] Finding natural numbers having n Trailing Zeroes in Factorial

问题描述

我需要以下问题的帮助.

给定整数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尾随零的数字.

谢谢

解决方案

要有效地获取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会产生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.

I need help with the following problem.

Given an integer m, I need to find the number of positive integers n and the integers, such that the factorial of n ends with exactly m zeroes.

I wrote this code it works fine and i get the right output, but it take way too much time as the numbers increase.

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

Could someone suggest me a more efficient way to do this. Presently, it takes 30 seconds for a test case asking for numbers with 250 trailing zeros in its factorial.

Thanks

解决方案

To get number of trailing zeroes of n! efficiently you can put

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) 

In order to solve the problem (what numbers have n trailing zeroes in n!) you can use these facts:

• number of zeroes is a monotonous function: f(x + a) >= f(x) if a >= 0.
• if f(x) = y then x <= y * 5 (we count only 5 factors).
• if f(x) = y then x >= y * 4 (let me leave this for you to prove)

Then implement binary search (on monotonous function).

E.g. in case of 250 zeroes we have the initial range to test [4*250..5*250] == [1000..1250]. Binary search narrows the range down into [1005..1009].

1005, 1006, 1007, 1008, 1009 are all numbers such that they have exactly 250 trainling zeroes in factorial

Edit I hope I don't spoil the fun if I (after 2 years) prove the last conjecture (see comments below):

Each 5**n within facrtorial when multiplied by 2**n produces 10**n and thus n zeroes; that's why f(x) is

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

where [...] stands for floor or integer part (e.g. [3.1415926] == 3). Let's perform easy manipulations:

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

So far so good

 f(x) <= x / 4 

Or if y = f(x) then x >= 4 * y Q.E.D.

这篇关于在阶乘中找到具有n个尾随零的自然数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！