python - 需要多少个数字才能使返回值等于整数 N？

Question

需要找到满足给定整数 N 的最小数 P

 sum of f(x)>=N. where f(x)=f(1)+f(2)+.....+f(p) where f(a) is number of times a number and then its quotient is divisible by 5 for example 100 is divisible by 5 two times as 100/5=20 and 20/5=4 but 4 is not divisible so f(100)=2

其中函数定义为数字与其商可以除以 5 的次数。例如对于 N=6 P 将是 25 因为 1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24不能被 5 整除并且 5 只能被 1 整除所以

f(5)=1,and same
f(10)=1,
f(15)=1,
f(20)=1
(20/5=4 but 4 is not divisible by 5) but 25 is divisible by 5

自从两次 25/5=5 和 5/5 =1) 所以 f(25)=2 所以 f(x)=f(1)+f(2)+.....f(25)=6

这是答案，所以最小的 P 应该是 25。这是我的代码，但在某些情况下我遇到了问题。

def myround(x, base=5):
    return ((base * round((x)/base)))

n=int(input())
count=0
i=5
while(n/i>=1):
    count+=1
    i=i*5
res=count+1
counter=0
for j in range(1,res+1):
    gcd_cal=((1/5)**j)
    counter+=gcd_cal
end_res=(n/counter)
zz=(myround(end_res))
reverse=zz-5
re=zz+5

counter1=0
for xx in range(1,res+1):
    div=int(5**xx)
    temp=(zz//div)
    counter1+=temp

counter2=0
for xx in range(1,res+1):
    div=int(5**xx)
    temp=(reverse//div)
    counter2+=temp

counter3=0
for xx in range(1,res+1):
    div=int(5**xx)
    temp=(re//div)
    counter3+=temp

if (counter1==n):
    print(zz)
elif(counter2==n):
    print(reverse)
elif(counter3==n):
    print(re)
else:
    print(max(zz,reverse,re))

注意:递归解决方案对于大 N 来说太慢了，比如 10**9

PS:我想知道需要多少个数字才能使返回值等于整数 N 比如说(例如 6)

编辑:DP解决这个问题可以

dict={}

def fa(x):
    if x in dict:
        return dict[x]
    if not x%5 and x%25 and x>0:  
        dict[x]=1
        return 1



    elif not x%5 and not x%25 and x>0:    
        dict[x]=1+fa(x//5)

        return 1+fa(x//5)
    else:
        return 0

def F(N):
    counter=0
    s=0 
    while s<N:

        counter+=5

        s+=fa(counter)
    return counter



for _ in range(int(input())):
    n=int(input())

    print(F(n))

Answer 1

这是一个具有常量存储并按 log(x) 次序运行的函数。我认为更小的存储或运行时间顺序是不可能的。

关键思想是将 x 视为类似于基数 5 的数字。找到数字 n 的 base-5 表示的一种方法是找到超过 n 的 5 的第一个幂，然后继续减少 5 的幂并找到多少这些符合数字 n。我的例程与此类似，但删除的是 5 的指数和而不是 5 的幂。由于简单的递推关系，求 n 的指数和很容易增加 5 的幂。可能有一种直接的方法可以找到所需的 5 的幂，但是我的函数的后半部分比那慢，所以优化我的函数的前半部分不会有太大的改进。

我已经针对 x 高达 10,000 的值测试了此例程，并且它进行了检查。它非常快，超过 x=10**100，尽管检查这些结果非常慢。请注意，我更喜欢将参数 n 用作整数值，而不是您的 x。

如果您需要更多解释，请告诉我。

def smallestsumexp5s(n):
    """Return the smallest integer whose sum of the exponents of 5 in
    the prime decomposition of i for 1 <= i <= n is greater than or
    equal to n.
    """
    # Find the power of 5 whose sum passes n
    powerof5 = 5
    sumofexpsof5 = 1
    while sumofexpsof5 <= n:
        powerof5 *= 5
        sumofexpsof5 = sumofexpsof5 * 5 + 1
    # Cut off pieces of the target to find the desired integer
    remains = n
    result = 0
    while remains > 0:
        # Back off to the previous power of 5
        powerof5 //= 5
        sumofexpsof5 //= 5
        # Cut off pieces of the remaining number
        q, remains = divmod(remains, sumofexpsof5)
        # Adjust the accumulated result
        result += q * powerof5
    return result