杜教筛

令 $f(x)$ 为某个积性函数，$s(n)=\sum\limits_{i=1}^nf(i)$，我们构造另一干函数 $g$ 算 $f*g$ 的前缀和。

$$
\begin{aligned}
\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}g(d)f(\dfrac{i}{d})=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}f(i)=\sum\limits_{d=1}^ng(d)s(\left\lfloor\dfrac{n}{d}\right\rfloor)
\end{aligned}
$$

我们的目标是 $s(n)$

我们发现：

$$
\begin{aligned}
g(1)s(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{d=2}^ng(d)s(\left\lfloor\dfrac{n}{d}\right\rfloor)
\end{aligned}
$$

我们需要算出 $(f*g)$ 的前缀和，通过对减号右边数论分块，我们需要算 $g$ 的前缀和，我们还需要算出 $g(1)$ 。所以关键在于 $g$ 函数的选取。

例子

• $\sum\limits_{i=1}^N\mu(i)$

不难发现我们这里应该选 $g$ 函数为 $I$ 。然后 $g$ 的前缀和为 $n$，$f*g$ 的前缀和是 $1$。

• $\sum\limits_{i=1}^N\phi(i)$

不难发现我们还是选 $g$ 为 $I$。然后 $g$ 的前缀和为 $n$，$f*g$ 的前缀和为 $\dfrac{n(n+1)}{2}$

• $\sum\limits_{i=1}^N\phi(i)\times i$

考虑有：

$$
\begin{aligned}
(f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})=\sum\limits_{d|n}\phi(d)\times d\times g(\dfrac{n}{d})
\end{aligned}
$$

考虑把 $d$ 消掉，所以我们不妨令 $g=id$，这样这个题就结束了。

• $\sum\limits_{i=1}^N\phi(i)\times i^2$

我们还是和上面一样，把它拆开：

$$
\begin{aligned}
(f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})=\sum\limits_{d|n}\phi(d)\times d^2\times g(\dfrac{n}{d})
\end{aligned}
$$

我们本着把 $d^2$ 消去的思路，不妨令 $g(x)=x^2$，这样就可以了。

复杂度证明

设 $k$ 以前的部分我们预处理，所以杜教筛的复杂度为：

$$
\sum\limits_{i=1}^{\frac{n}{k}}\sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\le \int_{1}^{\frac{n}{k}}\sqrt{n}x^{-\frac{1}{2}}dx=O(\frac{n}{\sqrt{k}})
$$

所以总复杂度应该为 $O(\frac{n}{\sqrt{k}}+k)$，显然 $k=n^{\frac{2}{3}}$ 的时候最优，所以总复杂度为 $O(n^\frac{2}{3})$ 。

相反，如果不预处理的话，相当于要对所有可能的 $\lfloor\frac{n}{i}\rfloor$ 做一个整数分块，一共有 $O(\sqrt{ n})$ 种取值，我们不妨认为这 $O(\sqrt n)$ 种取值为 $\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\cdots,\lfloor\frac{n}{\sqrt n}\rfloor$，实际上，整数分块得到的数不会超过 $2\sqrt{ n}$ 个，用这 $\sqrt{n}$ 个最大的值来估算显然是正确的。

所以时间复杂度约为：

$$
\int _1^{\sqrt{n}}\sqrt{\frac{n}{x}}dx=O(n^{\frac{3}{4}})
$$