令$d(n)$为$n$的约数的数量，并令 $$M(n,k)=\max_{n\le j\le n+k-1}d(j),$$ 以及 $$S(u,k)=\sum_{n=1}^{u-k+1}M(n,k),$$ 可以验证$S(1000,10)=17176$，求$S(10^8,10^5)$。

本题难度:

解答

本题主要考察数据结构，要点是控制内存，有两处难点：

一是约数数量的计算，用筛法更有效，但空间开销太大，因而此处直接用sympy提供的函数计算。

二是动态更新$M(n,k)$的值，一般而言用延迟堆即可实现，但本题数据量较大，用堆或队列实现时空间开销很大，因此优化为对每种约数数量只记录该数量最后一次出现时所对应的数，用字典记录该对应关系，并保持键值有序，因此使用有序字典。

最终结果是51281274340。

注：因需使用sortedcontainers中提供的有序字典并使用sympy计算约数数量，以下代码为Python 3，代码中还打印了进度信息。

from sympy import divisor_count
from sortedcontainers import SortedDict

u=10**8
k=10**5

threshold=10*k

d=SortedDict()

for n in range(1,k):
    d[divisor_count(n)]=n

res=0
for n in range(k,u+1):
    d[divisor_count(n)]=n
    while d.peekitem()[1] < n-k+1:
        d.popitem()
    res+=d.peekitem()[0]
    if n%k==0:
        print(f"{n//k}/1000 completed, current result: {res}" )
    if len(d)>threshold:
        for i,(j,v) in enumerate(d.items()):
            if v < n-k+1:
                d.popitem(index=i)

print(res)