需要多少个数字使得它们的和等于整数N？

Question

需要找到最小的数字 P，使得给定整数 N

 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能够被5整除。

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）。

编辑：此问题的动态规划解决方案可以是：

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))

- john mich

---

如果 N=5 会发生什么？ - T C Molenaar

如果 n=5，f(5) 将返回 1，f(10) 将返回 1，f(15) 返回 1，f(20) 返回 1，而 f(25) 将返回 2。因此，对于 n=5，我将选择 25，因为我想要多计算 1 次。所以答案是 25。 - john mich

我的DP解法对于 N = math.pow(10,5) 或更小的情况都能正常工作，但对于 N > math.pow(10,5) 的情况速度较慢。 - john mich

你应该修复第一个示例的缩进。 - gionni

缩进已经修复！ - john mich

Answer 1

这是一个存储恒定且运行时间为log(x)的函数。我认为不可能有更小的存储或运行时间更低。

关键思想是将x类似于5进制数字处理。找到一个超过n的5的幂的方法是，先找到第一个超过n的5的幂，然后继续减少该5的幂并找出多少个符合数n。我的例程类似，但是删除了5的指数和而不是5的幂。由于简单的递归关系，对于不断增加的5的幂，找到n的指数和是很容易的。可能有一种直接找到所需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

- Rory Daulton

---

先生，您真棒！ - john mich