杜教筛可以在低于线性时间的复杂度内计算 S(n)=∑i=1nf(i)S(n)=\sum_{i=1}^{n}f(i)。

狄利克雷卷积：

∑i=1n(f∗g)(i)=∑i=1n∑d∣ig(d)f(id)=∑i=1ng(i)S(⌊ni⌋)\begin{aligned} \sum_{i=1}^{n}(f * g)(i) & =\sum_{i=1}^{n}\sum_{d \mid i}g(d)f\left(\frac{i}{d}\right)\\ & =\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned} g(1)S(n)=∑i=1ng(i)S(⌊ni⌋)−∑i=2ng(i)S(⌊ni⌋)=∑i=1n(f∗g)(i)−∑i=2ng(i)S(⌊ni⌋)\begin{aligned} g(1)S(n) & = \sum_{i=1}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - \sum_{i=2}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\ & = \sum_{i=1}^n (f * g)(i) - \sum_{i=2}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned}

所以我们需要构造数论函数 gg：

  • 可以快速计算 ∑i=1n(f∗g)(i)\sum_{i=1}^n(f * g)(i)。

  • 可以快速计算 gg 的前缀和，以用数论分块求解 ∑i=2ng(i)S(⌊ni⌋)\sum_{i=2}^ng(i)S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)。

P4213 【模板】杜教筛

P4213 【模板】杜教筛。

莫比乌斯函数

利用这个：

ε=I∗μ\varepsilon=I*\mu

∑d∣nμ(d)=ε(n)\displaystyle\sum\limits_{d \mid n}\mu(d)=\varepsilon(n)

将 f=μf=\mu，g=Ig=I，h=εh=\varepsilon 代入：

I(1)S_{\mu}(n) &= \sum\limits_{i=1}^{n}\varepsilon(i)-\sum\limits_{i=2}^{n}I(i)S_{\mu}\left( \left\lfloor\frac{n}{i}\right\rfloor \right)\\ S_{\mu}(n)&=1-\sum\limits_{i=2}^{n}S_{\mu}\left( \left\lfloor\frac{n}{i}\right\rfloor \right). \end{aligned}$$ ### 欧拉函数 利用这个：

id=I*\varphi

\sum_{d|n}\varphi(d)=n

将 $f=\varphi$，$g=I$，$h=\mathrm{id}$ 代入： $$\begin{aligned} I(1)S_{\varphi}(n) &= \sum\limits_{i=1}^{n}\mathrm{id}(i)-\sum\limits_{i=2}^{n}I(i)S_{\varphi}\left( \left\lfloor\frac{n}{i}\right\rfloor \right)\\ S_{\varphi}(n) &= \frac{n(n+1)}{2}-\sum\limits_{i=2}^{n}S_{\varphi}\left( \left\lfloor\frac{n}{i}\right\rfloor \right). \end{aligned}$$ --- 时间复杂度是 $O(n^\frac{3}{4})$ 的，加上线性筛可以优化到 $O(n^\frac{2}{3})$。