(懒得重写了……直接把51nod上我的那篇博客贴过来好了)
(注:以下出现的所有$sigma_k(n)$均表示$sum_{d|n}d^k$,即$n$的所有约数的$k$次幂之和)
egin{align} Ans=&sum_{i=1}^nsum_{j=1}^nsigma_1(i j) end{align}
要化简这个式子首先要用到一个结论:
egin{align} sigma_1(i j)=sum_{p|i}sum_{q|j}[(p,q)=1]frac{p j}q end{align}
至于证明嘛,大致的思路就是每个质因子互相独立,因此对每个质因子分别考虑,把$i j$拆成$prod p_i^{a_i+b_i}$的形式,最后化简得到这个结果
把这个结论代入原式,得到
egin{align} Ans=&sum_{i=1}^nsum_{j=1}^nsigma_1(i j)\ =&sum_{i=1}^nsum_{j=1}^nsum_{p|i}sum_{q|j}[(p,q)=1]frac{p j}q\ =&sum_{d=1}^nmu(d)sum_{i=1}^nsum_{j=1}^nsum_{p|i}sum_{q|j}[d| (p,q)]frac{p j}qqquad(莫比乌斯反演)\ =&sum_{d=1}^nmu(d)sum_{d|p}sum_{d|q}frac p qsum_{p|i}sum_{q|j}j\ =&sum_{d=1}^nmu(d)sum_{d|p}sum_{d|q}frac p qleftlfloorfrac n p
ight
floor qfrac{leftlfloorfrac n q
ight
floorleft(leftlfloorfrac n q
ight
floor+1
ight)}2\ =&sum_{d=1}^nmu(d)sum_{d|p}pleftlfloorfrac n p
ight
floorsum_{d|q}frac{leftlfloorfrac n q
ight
floorleft(leftlfloorfrac n q
ight
floor+1
ight)}2\ =&sum_{d=1}^nmu(d)dleft(sum_{p=1}^{leftlfloorfrac n d
ight
floor}pleftlfloorfrac n{d p}
ight
floor
ight)left(sum_{q=1}^{leftlfloorfrac n d
ight
floor}frac{leftlfloorfrac n{d q}
ight
floorleft(leftlfloorfrac n{d q}
ight
floor+1
ight)}2
ight) end{align}
这个式子已经是分块形式了,现在只需要快速求出$mu(d)$和后面那两个东西的前缀和即可
先看一看后面的东西是什么,为了方便起见,先把$leftlfloorfrac n d
ight
floor$换成$n$,也就是说求这两个东西:
egin{align} &sum_{i=1}^n ileftlfloorfrac n i
ight
floor\ &sum_{i=1}^nleftlfloorfrac n i
ight
floorleft(leftlfloorfrac n i
ight
floor+1
ight) end{align}
先看前面那个东西,注意到$leftlfloorfrac n d
ight
floor$的实际意义就是$le n$的所有数中是$i$的倍数的数的个数,不难得到
egin{align} sum_{i=1}^n ileftlfloorfrac n i
ight
floor=sum_{i=1}^nsigma_1(i) end{align}
然后考虑后面那个东西,可以对它进行一些简单的变形:
egin{align} &sum_{i=1}^nleftlfloorfrac n i
ight
floorleft(leftlfloorfrac n i
ight
floor+1
ight)\ =&sum_{i=1}^nsum_{j=1}^{leftlfloorfrac n i
ight
floor}j\ =&sum_{j=1}^n jsum_{i=1}^{leftlfloorfrac n j
ight
floor}1\ =&sum_{i=1}^n ileftlfloorfrac n i
ight
floor end{align}
发现它跟上一个东西是一样的,因此
egin{align} Ans=sum_{d=1}^nmu(d)dleft(sum_{i=1}^{leftlfloorfrac n i
ight
floor}sigma_1(i)
ight)^2 end{align}
(ps:结果如此简洁)
现在只需要求出$mu(d)d$和$sigma_1(i)$的前缀和就行了,设$f(d)=mu(d)d$,则有$f*id=e$(写成代数形式就是$sum_{d|n}df(frac n d)=[n=1]$,这个不难验证),因此
egin{align} S_f(n)=1-sum_{d=2}^n d S_fleft(leftlfloorfrac n d
ight
floor
ight) end{align}
直接上杜教筛即可。
至于$sigma_1(i)$的前缀和,可以用和杜教筛类似的思路,先用线性筛预处理出前$n^{frac 2 3}$项,后面的$n^{frac 1 3}$项直接用原来的那个$sum_{i=1}^nsigma_1(i)=sum_{i=1}^n ileftlfloorfrac n i
ight
floor$算即可,单次计算是$sqrt n$的,复杂度和杜教筛的分析类似,最后可以得到复杂度和杜教筛相同,都是$O(n^{frac 2 3})$。
注意杜教筛自带分块形式,因此外面套一层分块不会影响复杂度,总复杂度仍为$O(n^{frac 2 3})$。