真是一道“简单”的数学题呢~
反演题, 化式子.
[ans=sum_{i=1}^nsum_{j=1}^nijgcd(i,j) \ =sum_{i=1}^nsum_{j=1}^nsum_{d=1}^nij[gcd(i,j)=d]\ =sum_{d=1}^ndsum_{i=1}^nsum_{i=1}^nij[gcd(i,j)=1]\ =sum_{d=1}^nd^3sum_{i=1}^{left lfloor frac nd
ight
floor}sum_{j=1}^{left lfloor frac nd
ight
floor}ij[gcd(i,j)=1] \ =sum_{d=1}^nd^3sum_{i=1}^{left lfloor frac nd
ight
floor}isum_{j=1}^{left lfloor frac nd
ight
floor}j[gcd(i,j)=1] \ =sum_{d=1}^nd^3sum_{i=1}^{left lfloor frac nd
ight
floor}isum_{j=1}^{left lfloor frac nd
ight
floor}jsum_{t|i,j}mu(t) \ i=tp,j=tq,\ =sum_{d=1}^nd^3sum_{t=1}^{left lfloor frac nd
ight
floor}t^2cdotmu(t)sum_{p=1}^{left lfloor frac n{td}
ight
floor}psum_{q=1}^{left lfloor frac n{td}
ight
floor}q \ ecause sum_{i=1}^n=frac {n(n+1)}2\ herefore ans=sum_{d=1}^nd^3sum_{t=1}^{left lfloor frac nd
ight
floor}t^2cdotmu(t)[frac{n(n+1)}{2}]
]
然后我们令(T=id), 枚举(T),
[ans=sum_{T=1}^n[frac{left lfloor frac nT
ight
floor(left lfloor frac nT
ight
floor+1)}{2}]^2sum_{d|T}d^3(frac Td)^2mu(frac Td) \
=sum_{T=1}^n[frac{left lfloor frac nT
ight
floor(left lfloor frac nT
ight
floor+1)}{2}]^2T^2sum_{d|T}dmu(frac Td) \
=sum_{T=1}^n[frac{left lfloor frac nT
ight
floor(left lfloor frac nT
ight
floor+1)}{2}]^2T^2(n*mu)(T) \
=sum_{T=1}^n[frac{left lfloor frac nT
ight
floor(left lfloor frac nT
ight
floor+1)}{2}]^2T^2varphi(T)
]
然后我们令(X=[frac{left lfloor frac nT ight floor(left lfloor frac nT ight floor+1)}{2}]^2, f(T)=T^2varphi(T)), 这样就变成了
[ans=sum_{T=1}^nXf(T)
]
(X)可以分块然后(O(1))算, 那我们只要能求出(f(T))的前缀和就行了.
那(n<=10^{10})要用杜教筛. 我们想一下杜教筛的通式:
[s_f(x)=frac{s_{f*g}(x)-sum_{i=2}^ns_f(left lfloor frac ni
ight
floor)g(i)}{g(1)}
]
其中(g(x))和((f*g)(x))是易求前缀和的函数.
看到这种乘积的前缀和我们又想到了之前做lcm之和的提出乘积中某一项的高端操作, 我们就试着让(g(x))去卷(n^2)(就是(f(x)=x^2)啦).
然后
[g(x)=(n^2cdotvarphi)(x) \
(g*n^2)(x)=((n^2cdotvarphi)*n^2)(x)=(n^2cdot(varphi*1))(x)=(n^2cdot n)(x)=n^3(x)
]
然后(n^3(x))的前缀和也是有公式的可以(O(1))算, 这样我们就令(g(x)=n^2(x), (f*g)(x)=n^3(x)), 然后扔到上面的杜教筛通式里做就好啦~
复杂度可能是(O(sqrt n*n^{frac 23}))的, 不过这应该是最优的复杂度了..
代码应该不太好写, 懒得写了QAQ