小编Kha*_*led的帖子

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

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

Run Code Online (Sandbox Code Playgroud)

找到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  = …

这是python中的代码:

# function for pentagonal numbers
def pent (n):     return int((0.5*n)*((3*n)-1))

# function for generalized pentagonal numbers
def gen_pent (n): return pent(int(((-1)**(n+1))*(round((n+1)/2))))

# array for storing partitions - first ten already stored
partitions = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42]

# function to generate partitions 
def partition (k):
 if (k < len(partitions)): return partitions[k]

 total, sign, i = 0, 1, 1

 while (k - gen_pent(i)) >= 0:
  sign   = (-1)**(int((i-1)/2))
  total += sign*(partition(k - gen_pent(i))) …