用于求数论函数的前缀和。
基本的
杜教筛就是这么一个柿子： \[ S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^n g(i)S(\lfloor\frac{n}{i}\rfloor) \] 让我们求一个数论函数 \(f\) 的前缀和 \(S(n)=\sum_{i=1}^n f(i)\) 时，找一个合适的数论函数 \(g\)： \[ \begin{aligned} &\quad \sum_{i=1}^n(f*g)(i)\\ &=\sum_{i=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)\\ &=\sum_{d=1}^n g(d)S(\lfloor\frac{n}{d}\rfloor)\\ \end{aligned} \] \(g\) 函数要满足 \(f*g\) 的前缀和是很容易得到的，这样求 \(g(1)S(n)\) 时， \[ g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^n g(i)S(\lfloor\frac{n}{i}\rfloor) \] 所有积性函数都满足 \(g(1)=1\)，就可以忽略 \(g(1)\)。
最右边那项可以整除分块，\(S(\lfloor\frac{n}{i}\rfloor)\) 递归求解。
对于小于 \(n^{\frac{2}{3}}\) 的线性预处理，递归的加上 unordered_map / map 记忆化。
这样复杂度为 \(\mathcal O(n^{\frac{2}{3}})\)，我又不会证。
一些例子
\(\varphi\)
\[ \varphi*I=id \] \[ S_{\varphi}(n)=\sum_{i=1}^n i-\sum_{i=2}^n S_{\varphi}(\lfloor\frac{n}{i}\rfloor) \]
\(\mu\)
\[ \mu*I=\epsilon \] \[ S_{\mu}(n)=1-\sum_{i=2}^n S_{\mu}(\lfloor\frac{n}{i}\rfloor) \]
\(\sigma_k\)
其中 \(\sigma_k(n)=\sum_{d|n}d^k\)。 \[ \sigma_k=id_k*I \]
\[ \sum_{i=1}^n \sigma_k(i)=\sum_{i=1}^ni^k\lfloor\frac{n}{i}\rfloor \]
常用 \(S_{id_k}(n)\) 公式： \[ \begin{aligned} S_{id}(n)&=\frac{n(n+1)}{2}\\ S_{id_2}(n)&=\frac{n(n+1)(2n+1)}{6}\\ S_{id_3}(n)&=\Big(\frac{n(n+1)}{2}\Big)^2\\ S_{id_k}(n)&=\frac{1}{k+1}\bigg((n+1)^{t+1}-\sum_{j=0}^{t-1}\binom{t+1}{j}S_{id_j}(n)\bigg)\\ \end{aligned} \]
\(\varphi\cdot id_k\)
当 \(C\) 是完全积性函数时，\((A\cdot C)*(B\cdot C)=(A*B)\cdot C\)。 \[ (\varphi\cdot id_k)*(I\cdot id_k)=(\varphi* I)\cdot id_k=id_{k+1} \]
\[ S_{\varphi\cdot id_k}(n)=\sum_{i=1}^ni^{k+1}-\sum_{i=2}^ni^kS_{\varphi\cdot id_k}(\lfloor\frac{n}{i}\rfloor) \]
\(\mu\cdot id_k\)
同理。 \[ (\mu\cdot id_k)*(I\cdot id_k)=(\mu*I)\cdot id_k=\epsilon \]
\[ S_{\mu\cdot id_k}(n)=1-\sum_{i=2}^ni^kS_{\mu\cdot id_k}(\lfloor\frac{n}{i}\rfloor) \]
\(\mu^2*(\mu\cdot id)\) \[ (\mu^2*(\mu\cdot id))*id=\mu^2*((\mu\cdot id)*(I\cdot id))=\mu^2 \]
\[ S_{\mu^2*(\mu\cdot id)}(n)=S_{\mu^2}(n)-\sum_{i=2}^n iS_{\mu^2*(\mu\cdot id)}(\lfloor\frac{n}{i}\rfloor) \]
\(S_{\mu^2}(n)\) 可以 \(\mathcal O(\sqrt{n})\) 求，见 P4318 完全平方数。