在数论题目中，常常需要根据一些 积性函数 的性质，求出一些式子的值。

积性函数：对于函数 $f(n)$ 有 $f(1)=1$ 且对于所有互质的 $a$ 和 $b$，总有 $f(ab)=f(a)f(b)$，则称 $f(n)$ 为积性函数。

常见的积性函数有：

• $\sigma_0(n)=d(n)=\sum_{d\mid n }1$
• $\sigma(n)=\sum_{d\mid n}d$
• $\varphi(n)=\sum_{i=1}^n[\gcd(x,i)=1]$
• $\mu(n)=\begin{cases}1&\ n=1\\(-1)^k&\ \prod_{i=1}^k q_i=1\\0 &\ \max\{q_i\}>1 \end{cases}$

积性函数有如下性质：

若 $f(n)$，$g(n)$ 为积性函数，则：

• $h(n)=f(n^p)$
• $h(n)=f^p(n)$
• $h(n)=f(n)g(n)$
• $h(n)=\sum_{d\mid n}f(d)g(\frac n d)$

中的 $h(n)$ 也为积性函数。

在莫比乌斯反演的题目中，往往要求出一些数论函数的前缀和，利用 杜教筛 可以快速求出这些前缀和。

杜教筛被用来处理数论函数的前缀和问题。对于求解一个前缀和，杜教筛可以在低于线性时间的复杂度内求解

对于数论函数 $f$，要求我们计算 $S(n)=\sum_{i=1}^nf(i)$.

我们想办法构造一个 $S(n)$ 关于 $S\left(\left\lfloor\frac n i\right\rfloor\right)$ 的递推式

对于任意一个数论函数 $g$，必满足 $$ \sum_{i=1}^{n}\sum_{d \mid i}f(d)g\left(\frac{i}{d}\right)=\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\\ \Leftrightarrow \sum_{i=1}^{n}(f\ast g)(i)=\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) $$

略证：

$f(d)g(\frac i d)$ 就是对所有 $i\le n$ 的做贡献，因此变换枚举顺序，枚举 $d,\frac i d$（分别对应新的 $i,j$） $$ \begin{split} &\sum_{i=1}^n\sum_{d\mid i}f(d)g\left(\frac i d\right)\\ =&\sum_{i=1}^n\sum_{j=1}^{\left\lfloor\frac n i\right\rfloor}g(i)f(j)\\ =&\sum_{i=1}^ng(i)\sum_{j=1}^{\left\lfloor\frac n i\right\rfloor}f(j)\\ =&\sum_{i=1}^ng(i)S\left(\left\lfloor\frac n i\right\rfloor\right) \end{split} $$ 那么可以得到递推式 $$ g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S\left(\left\lfloor\frac n i\right\rfloor\right) $$ 那么假如我们可以快速对 $\sum_{i=1}^n(f*g)(i)$ 求和，并用数论分块求解 $\sum_{i=2}^ng(i)S\left(\left\lfloor\frac n i\right\rfloor\right)$，就可以在较短时间内求得 $g(1)S(n)$。