0401 约数平方和
* * * *
拉格朗日计划
* * * *
约数平方和

6的约数是1、2、3和6,这些数的平方和是$1+4+9+36=50$。

记$\sigma_2(n)$为n所有约数的平方和,例如$\sigma_2(6)=50$。

再记$S_n=\sum_{i=1}^n\sigma_2(i)$,其前六项为1、6、16、37、63、113。

求$S_{10^{15}}$的最后九位数字。

本题难度:



解答

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