python - 一系列数字的内部总和

Question

我所说的内和是指例如123的内和等于1+2+3=6

假设我有两个数字表示一个(包含)范围，a 和 b，它们是我从标准输入获得的，我想添加该范围内所有数字的内部总和。我的解决方案:

a, b = sys.stdin.readline().split()
a = int(a)
b = int(b)
s = 0
for x in range(a, b+1):
    t = str(x)
    s = s + sum([int(i) for i in t])
print(s)

工作正常。但是有没有更快的方法呢？我觉得 list-comprehension 的使用很慢，所以我想在这里输入一些信息。

Answer 1

如果a和b足够大，可以使用下面的方法。如果 a 和 b 的最大长度为 n(a 或 b 中的数字个数)，则复杂度为 O(n*10*n)。因此，如果数字(a 或 b)为 10^9，则复杂度约为 (9*9*10)=810

我首先计算所有数字的数字总和到 b (summation(b))，然后我找到所有数字的数字总和到 a-1(summation(a-1))。然后我计算了通过求和(b)-求和(a-1)得到期望的结果。

import sys
def power(x):
    po=1
    for i in range(x):
        po=po*10
    return po
def summation(x):
    s=str(x)
    le=len(s)
    res=0
    carry=0
    for i in range(le):
        c=int(s[i])
        rem=le-i-1
        for j in range(c):
           res=res+((carry+j)*power(rem)+45*(rem)*power(rem-1))
        carry+=c
    res+=carry
    return res


a, b = sys.stdin.readline().split()
a = int(a)
b = int(b)
s = 0

#Bruteforce
for x in range(a, b+1):
    t = str(x)
    s = s + sum([int(i) for i in t])

#Optimized
res=summation(b)-summation(a-1)

print(res,s)