项目欧拉 - 问题160

Question

对于任何N,设f(N)为N!中尾随零之前的最后五位数.例如,

9!  = 362880 so f(9)=36288 
10! = 3628800 so f(10)=36288 
20! = 2432902008176640000 so f(20)=17664

找到f(1,000,000,000,000)

我已经成功地解决了这个问题给出的例子,我的函数可以正确找到f(9),f(10)等.但是它会遇到更大的数字,尤其是问题要求的数字 - f(10 ^ 12) .

我目前的优化如下:我从乘数和总和中删除尾随零,并在每次乘法后将总和缩短为5位数.python中的代码如下:

def SFTR (n):
 sum, a = 1, 2
 while a < n+1:
  mul  = int(re.sub("0+$","",str(a)))
  sum *= mul
  sum  = int(re.sub("0+$","",str(sum))[-5:])
  a   += 1
 return sum 

任何人都可以告诉我为什么这个功能如此大规模扩展,以及为什么它需要这么长时间.此外,如果有人可以提示我正确的方向来优化我的算法.(一般主题的名称就够了)谢谢.

更新:

我已经对优化进行了一些更改,但速度明显更快,但对于f(10 ^ 12)来说仍然不够快.任何人都可以告诉我什么使我的代码变慢或如何使其更快？

def SFTR (n):
    sum, a = 1, 2
    while a < n+1:
        mul  = a

        while(mul % 10 == 0): mul = mul/10
        mul  = mul % 100000

        sum *= mul

        while(sum % 10 == 0): sum = sum/10
        sum  = sum % 100000

        a   += 1
    return sum

Answer 1

mul可以变得非常大.这有必要吗？如果我要求您手动计算1278348572934847283948561278387487189900038*38758的最后5个非零数字, 您确实需要知道的第一个数字到底有多少位数？