杜教筛（下）：狄利克雷卷积

定义：

$$
定义f,g$f,g$两个积性函数的狄利克雷卷积运算(*)为：

性质：

狄利克雷卷积满足：

1. 交换律：f∗g=g∗f$f\ast g=g\ast f$
2. 结合律：(f∗g)∗h=f∗(g∗h)$(f\ast g)\ast h=f\ast (g\ast h)$
3. 分配律：f∗(g+h)=f∗h+g∗h$f\ast (g+h)=f\ast h+g\ast h$
4. 单位元：f∗e=f$f\ast e=f$

常见函数卷积：

μ∗1=ϵ$\mu \ast 1=ϵ$ (莫比乌斯函数与1互为逆元)
ϕ∗1=Id$\varphi \ast 1=Id$ (欧拉函数与n互为逆元)
ϕ=Id∗μ$\varphi =Id\ast \mu$ (莫比乌斯与欧拉的关系)

d=1∗1$d=1\ast 1$
1=μ∗d$1=\mu \ast d$

$$

---

$$

杜教筛：

由于涉及内容太多，分成两篇博客进行讲述，建议先看前一篇，就当你已经看完前一篇了，我这里会讲的快一点

求∑ni=1f(i)$\sum _{i=1}^{n}f(i)$，设为Ans(n)$Ans(n)$

找一个积性函数g(x)，那么

前一篇中有理论证明，这里对出数学证明，显然：那么：接下来和前一篇一样： 结论：

按照上一篇的说法，递归+整除分块+线性筛 收尾。

$$

---

$$

例题：

求∑ni=1ϕ(i)∗i$\sum _{i=1}^n\varphi (i)\ast i$

显然，如果卷一个函数1的话，变成∑ni=1∑d|iϕ(d)∗d$\sum _{i=1}^n\sum _{d|i}\varphi (d)\ast d$，好像并没有什么简单的化简，而卷一个函数Id$Id$的话，就变成了

而∑d|iϕ(d)=i$\sum _{d|i}\varphi (d)=i$，所以得到：这题就变得异常简单了

总结：

当求积性函数前缀和不好求的时候，用狄利克雷卷上一个积性函数，使卷完后的式子的前缀和变得简单，卷完后的前缀和算出来基本上题目就完成了

• 如果出现ϕ(x)$\varphi (x)$，那么就凑∑d|nϕ(d)=n$\sum _{d|n}\varphi (d)=n$
• 如果是u(x)$u(x)$，就凑∑n≠1d|nu(d)=0$\sum _{d|n}^{n\ne 1}u(d)=0$