python - spoj.FCTRL 超出时间限制

Question

我必须生成整数阶乘末尾尾随零的数量。第一个输入是测试用例“T”的编号。接下来的 T 行包含输入整数。输出应在输入整数的阶乘末尾包含零的数量。这是我的代码，但它超出了时间限制。请帮我优化。

T=int(raw_input())
a=[]
for i in range(0,T):

    a.append(int(raw_input()))
def factorial (n):
    fact=1
    while(n>0):
        fact=fact*n
        n=n-1
    return fact

b=[]
for i in range(0,T):
    b.append(factorial(a[i]))


c=[]

for i in range(0,T):
    ans=0
    while(b[i]%10 == 0):
        ans=ans+1
        b[i]=b[i]/10
    c.append(ans)
for i in range(T):
    print c[i],

Answer 1

由于输入数字很大，您无法计算它们的阶乘。时间太长了。考虑一下计算尾随 0 的数量而不计算阶乘的算法。事实上，每个尾随 0 都是在 5 乘以一些偶数之后出现的。因此，您需要计算所有数字中 5 个因子的数量，以降低输入。

例如27!以 6 个零结尾，因为在 (1, 27) 5 范围内，因子只有这些数字

5(1) 10(1) 15(1) 20(1) 25(2)。 25 有两个 5 的因数。