本题似乎直接用以下公式求和最为简洁
$$S(n)=\sum_{d=1}^{N^2}d\sum_{x=1}^N\lfloor\frac{N}{\gcd(x,d)}\rfloor,$$
以下改编自官方论坛，最终结果为$968697378$。
注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。代码需要数小时运行，且递归实现难以打印进度，需耐心等待。
from functools import *
N=10**11
mod=10**9
f=lambda x: x*(x+1)//2
@cache
def S(x):
a=b=0
u=1
while u <= x:
y=x//u
v=x//y
a+=y*(f(v)-f(u-1))
b+=f(y)*(v-u+1)
u=v+1
r=a*b
u=2
while u <= x:
y=x//u
v=x//y
r-=S(y)*(f(v)-f(u-1))
u=v+1
return r
print(S(N)%mod)
|
