根据OEIS A064602中的信息有
$$S_n=\sum_{i=1}^ni^2\lfloor\frac{n}{i}\rfloor,$$
因此只需根据$\lfloor\frac{n}{i}\rfloor$的值分块计算即可。
最终结果是$281632621$。
注:为便于区分除法,以下代码为Python 3。运行需要数分钟但未打印进度信息。
target=10**15
m=10**9
f=lambda n:(n*(n+1)*(2*n+1)//6)%m
r=0
x=1
while x*x <= target:
r=(r+target//x*x*x)%m
x+=1
while x <= target:
y=target//(target//x)
r=(r+(f(y)-f(x-1))*(target//x))%m
x=y+1
print(r)
|