杜教筛

一些积性函数：

$mu(n)$：莫比乌斯函数

$varphi(n)$：欧拉函数

$d(n)$：约数个数

$sigma(n)$：约数和函数

$epsilon(n)$：一元函数，$epsilon(n)=[n==1]$

$I(n)$：恒等函数，$I(n)=1$

$id(n)$：单位函数，$id(n)=n$

狄利克雷卷积：

• 定义两个数论函数 $f$ 和 $g$ 的狄利克雷卷积为：$(f*g)[n]=sum_{d|n}f(d)cdot g(frac n d)$
• 运算规律：交换律、结合律、分配律

杜教筛用于解决一类特殊的积性函数前缀和，即：$sumlimits_{i=1}^n f(i)$.

我们构造两个积性函数 $g$ 和 $h$，使得 $h=f*g$；同时我们记 $S(n)=sumlimits_{i=1}^n f(i)$：

$$begin{align} sum_{i=1}^n h(i)&=sum_{i=1}^nsum_{d|n} g(d)f(frac i d)\ &=sum_{d=1}^ng(d)sum_{i=1}^{lfloorfrac n drfloor}f(i)\ &=sum_{d=1}^ng(d)cdot S(lfloorfrac n drfloor) end{align}$$

将 $S(n)$ 一项移到左边，就有：

$$begin{align} S(n)=sum_{i=1}^n h(i)-sum_{d=2}^n g(d)cdot S(lfloorfrac n drfloor) end{align}$$

那么，如果我们能够快速计算出 $h$ 的前缀和，并且预处理 $S$ 的前 $n^{frac 2 3}$ 项，就能够在 $mathcal{O(n^{frac 2 3})}$ 的复杂度内解决问题。