容易验证
$$S(1,m)=\frac{m(m+1)}{2}-\sum_{d=2}^mS(1,\lfloor\frac{m}{d}\rfloor),$$
以及若p是素数且p不整除q，则有
$$S(pq,m)=(p-1)S(q,m)+S(pq,\lfloor\frac{m}{p}\rfloor).$$
而
$$510510=2\times 3\times 5\times 7\times 11\times 13\times 17.$$
因此递归计算即得结果$754862080$。
注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。递归中难以打印进度，大约运行十多分钟能得到结果。
from functools import *
@cache
def S(n):
if n==1:
return 1
r=n*(n+1)//2
k=1
while k*(k+1) < n:
r-=S(k)*(n//k-n//(k+1))
k+=1
d=n//k
while d>1:
r-=S(n//d)
d-=1
return r
def cal(L,n):
if L:
return 0 if n==0 else (L[0]-1)*cal(L[1:],n)+cal(L,n//L[0])
return S(n)
print(f"{cal([2,3,5,7,11,13,17],10**11)%(10**9)}")
|
