也许更好的阅读体验

作用与使用前提

对一个积性函数 $f$f，我们要求 $f$f的前 $n$n项和 $S_n$Sn​，并且要求在比线性复杂度更低的复杂度情况下求出
若有数论函数 $g,h$g,h，满足
$h=f\ast g$h=f∗g
其中 $\ast$∗为狄利克雷卷积
并且 $h$h的前缀非常好求， $g$g的单项非常好求，我们就可以快速的求出 $f$f的前缀和

求法

先看 $f,g,h$f,g,h的关系
$\begin{array}{c}{\displaystyle h\left(n\right)=\sum _{d\mid n}f\left(\frac{n}{d}\right)g\left(d\right)}\end{array}$h(n)=d∣n∑​f(dn​)g(d)​
我们把对 $h$h求前缀和，则有
$\begin{array}{cc}{\displaystyle \sum _{i=1}^{n}h\left(i\right)}& {\displaystyle =\sum _{i=1}^{n}f\ast g\left(i\right)}\\ {\displaystyle }& {\displaystyle =\sum _{i=1}^n\sum _{dli}f\left(\frac{n}{a}\right)g\left(d\right)}\\ {\displaystyle }& {\displaystyle =\sum _{d=1}^{n}g\left(d\right)\sum _{i=1}^{\frac{n}{d}}f\left(i\right)}\\ {\displaystyle }& {\displaystyle =\sum _{d=1}^{n}g\left(d\right)S_{\frac{n}{d}}}\\ {\displaystyle }\end{array}$i=1∑n​h(i)​=i=1∑n​f∗g(i)=i=1∑n​dli∑​f(an​)g(d)=d=1∑n​g(d)i=1∑dn​​f(i)=d=1∑n​g(d)Sdn​​​
接下来我们把 $d=1$d=1的情况单独提出来

$\begin{array}{cc}{\displaystyle \sum _{i=1}^{n}h\left(i\right)}& {\displaystyle =g\left(1\right)S_n+\sum _{d=2}^{n}g\left(d\right)S_{\frac{n}{d}}}\end{array}$i=1∑n​h(i)​=g(1)Sn​+d=2∑n​g(d)Sdn​​​

再把 $S_n$Sn​写到左边
$\begin{array}{c}{\displaystyle S_n=\frac{\left(\sum _{i=1}^{n}h\left(i\right)\right)-\left(\sum _{i=2}^{n}g\left(i\right)S_{\frac{n}{i}}\right)}{g\left(1\right)}}\end{array}$Sn​=g(1)(∑i=1n​h(i))−(∑i=2n​g(i)Sin​​)​​
对一般的数论函数 $g$g，通常 $g\left(1\right)=1$g(1)=1，于是我们可以把 $g\left(1\right)$g(1)省掉，得到
$\begin{array}{c}{\displaystyle S_n=\left(\sum _{i=1}^{n}h\left(i\right)\right)-\left(\sum _{i=2}^{n}g\left(i\right)S_{\frac{n}{i}}\right)}\end{array}$Sn​=(i=1∑n​h(i))−(i=2∑n​g(i)Sin​​)​

于是我们可以先预处理出来 $S_1,S_2,\cdots S_m$S1​,S2​,⋯Sm​， $m$m取一个较大的数，如 $10^6$106
之后我们可以通过记忆化搜索的方法来求解 $S_n$Sn​

举例

$\mu$μ

我们要求 $\mu$μ的前缀和，即 $f=\mu$f=μ
我们知道 $I=\xi \ast \mu$I=ξ∗μ
其中 $\xi \left(n\right)=1,I\left(n\right)=[n=1]$ξ(n)=1,I(n)=[n=1]
那么
$\begin{array}{cc}{\displaystyle S_{\mu \left(n\right)}}& {\displaystyle =\left(\sum _{i=1}^{n}I\left(i\right)\right)-\left(\sum _{i=2}^n\xi \left(i\right)S_{\mu \left(\frac{n}{i}\right)}\right)}\\ {\displaystyle }& {\displaystyle =1-\sum _{i=2}^n{S}_{\mu \left(\frac{n}{i}\right)}}\end{array}$Sμ(n)​​=(i=1∑n​I(i))−(i=2∑n​ξ(i)Sμ(in​)​)=1−i=2∑n​Sμ(in​)​​

$\phi$φ

或者要求 $\phi$φ的前缀和，即 $f=\phi$f=φ
我们知道 $\phi$φ的一条性质
$\begin{array}{c}{\displaystyle n=\sum _{d\mid n}\phi \left(d\right)}\end{array}$n=d∣n∑​φ(d)​
然后我们知道一个数论函数 $id$id并且 $id\left(n\right)=n$id(n)=n
于是这条性质我们也可以写成
$id=\phi \ast \xi$id=φ∗ξ
我们再套上面的公式，即可得到
$\begin{array}{cc}{\displaystyle S_{\phi \left(n\right)}}& {\displaystyle =\left(\sum _{i=1}^{n}id\left(i\right)\right)-\left(\sum _{i=2}^n\xi \left(i\right)S_{\phi \left(\frac{n}{i}\right)}\right)}\\ {\displaystyle }& {\displaystyle =\frac{n(1+n)}{2}-\sum _{i=2}^n{S}_{\phi \left(\frac{n}{i}\right)}}\end{array}$Sφ(n)​​=(i=1∑n​id(i))−(i=2∑n​ξ(i)Sφ(in​)​)=2n(1+n)​−i=2∑n​Sφ(in​)​​

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧