杜教筛(推导方法)

杜教筛求积性函数的前缀和$O(n^{\frac{3}{4}})$，预处理后的时间复杂度$O(n^{\frac{2}{3}})$

一般的推导过程

$(f\ast g)(n)=g(d)f(\frac{n}{d})$是两个数论函数的卷积
$$\begin{gathered} \sum _{i=1}^n(f\ast g)(i)=\sum _{i=1}^n\sum _{d|i}g(d)f(\frac{i}{d}) \\ =\sum _{d=1}^n\sum _{d|i}g(d)f(\frac{i}{d}) \\ =\sum _{d=1}^{n}g(d)\sum _{d|i}f(\frac{i}{d}) \\ =\sum _{d=1}^{n}g(d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i) \end{gathered}$$
记$S(n)={\sum }_{i=1}^{n}f(i)$
$$\begin{gathered} \sum _{d=1}^{n}g(d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i) \\ =\sum _{d=1}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor ) \end{gathered}$$
由数论函数的性质可知，$g(1)=1$，那么
$$\begin{gathered} \sum _{i=1}^n(f\ast g)(i)=\sum _{d=1}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor ) \\ =\sum _{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )+g(1)\ast S(n) \\ =\sum _{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )+S(n) \end{gathered}$$
那么
$$S(n)=\sum _{i=1}^n(f\ast g)(i)-\sum _{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )$$

常见的卷积公式

${\sum }_{d|n}d=1\ast id$
$1\ast \mu =e$
$\phi \ast 1=id$
$\phi =id\ast \mu$

一些式子的总结

令$f(i)=i\phi (i)$
$(f\ast id)(n)={\sum }_{d|n}d\phi (d)\frac{n}{d}=n{\sum }_{d|n}\phi (d)=n^2$

令$f(i)=i\mu (i)$
$(f\ast id)(n)={\sum }_{d|n}d\mu (d)\frac{n}{d}=n{\sum }_{d|n}\mu (d)=n[n=1]$
$$\begin{gathered} S(n)=\sum _{i=1}^n\mu (i)=\sum _{i=1}^{{}^n}e(i)-\sum _{d=2}^{n}S(\lfloor \frac{n}{d}\rfloor ) \\ S(n)=\sum _{i=1}^{n}i\mu (i)=\sum _{i=1}^{n}n[n=1]-\sum _{d=2}^{n}dS(\lfloor \frac{n}{d}\rfloor ) \end{gathered}$$
$$\begin{gathered} S(n)=\sum _{i=1}^n\phi (i)=\sum _{i=1}^{n}id-\sum _{d=2}^{n}S(\lfloor \frac{n}{d}\rfloor ) \\ S(n)=\sum _{i=1}^{n}i\phi (i)=\sum _{i=1}^n(id{)}^2-\sum _{d=2}^{n}dS(\lfloor \frac{n}{d}\rfloor ) \\ .... \\ S(n)=\sum _{i=1}^n{i}^n\phi (i)=\sum _{i=1}^n(id{)}^{n+1}-\sum _{d=2}^n{d}^{n}S(\lfloor \frac{n}{d}\rfloor ) \end{gathered}$$