狄利克雷卷积

第一部分：狄利克雷卷积（Dirichlet Convolution）

它是数论函数空间上的二元运算，定义为： 对于两个数论函数$f(n)$和$g(n)$，它们的卷积$(f\ast g)(n)$为：

$$(f\ast g)(n)=\sum _{d|n}f(d)\cdot g\left(\frac{n}{d}\right)$$

（其中$d|n$表示$d$取遍$n$的所有正因子。）

1. 三大核心性质

• 交换律：$f\ast g=g\ast f$
• 结合律：$(f\ast g)\ast h=f\ast (g\ast h)$
• 分配律：$f\ast (g+h)=f\ast g+f\ast h$

2. 至关重要的“单位元”（恒等函数）

定义函数$ϵ(n)$（或写作$e(n)$）：

$$ϵ(n)=\{\begin{array}{ll}1& (n=1)\\ 0& (n>1)\end{array}$$

显然，对于任意函数$f$，都有：$f\ast ϵ=ϵ\ast f=f$。

3. 必须熟记的“四大基础积性函数”及其卷积关系

• $\mathbf{1}(n)$：常函数，恒等于$1$。
• $\text{Id}(n)$：恒等函数，$\text{Id}(n)=n$。
• $\phi (n)$：欧拉函数（$1$到$n$中与$n$互质的个数）。
• $\mu (n)$：莫比乌斯函数（下面会细讲）。

极重要的恒等式（一定要背下）：

1.$\phi \ast \mathbf{1}=\text{Id}$ 即：$\sum _{d|n}\phi (d)=n$

2.$\mu \ast \mathbf{1}=ϵ$ 即：$\sum _{d|n}\mu (d)=[n=1]=e$（这是莫比乌斯反演的根源）

---

第二部分：莫比乌斯函数（$\mu$）与反演

1. 莫比乌斯函数的定义

若$n=p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k}$（质因数分解）：

$$\mu (n)=\{\begin{array}{ll}1& (n=1)\\ (-1{)}^k& (a_1=a_2=\cdots =a_k=1，\text{即无平方因子数})\\ 0& (\text{存在某个 }{a}_i\ge 2，\text{即含有平方因子})\end{array}$$

2. 核心引理（反演的数学基础）

$$\sum _{d|n}\mu (d)=\{\begin{array}{ll}1& (n=1)\\ 0& (n>1)\end{array}$$

用卷积语言写就是：$\mu \ast \mathbf{1}=ϵ$。
这意味着，$\mu$ 是常函数$\mathbf{1}$在狄利克雷卷积下的逆元。

---

第三部分：莫比乌斯反演公式（两种形式）

形式一（约数形式，最常用）

如果数论函数$F(n)$和$f(n)$满足：

$$F(n)=\sum _{d|n}f(d)$$

即$F=f\ast \mathbf{1}$，那么：

$$f(n)=\sum _{d|n}\mu (d)\cdot F\left(\frac{n}{d}\right)$$

即：$f=F\ast \mu$。

形式二（倍数形式，常用于求和变换）

如果：

$$F(n)=\sum _{n|d}f(d)$$

（这里$d$是$n$的倍数，通常用在有限上界$N$中），那么：

$$f(n)=\sum _{n|d}\mu \left(\frac{d}{n}\right)\cdot F(d)$$

快速记忆口诀

已知“和函数”$F$求“原函数”$f$，就把$F$卷上$\mu$，把除数换成商。

---

第四部分：经典应用案例（数论竞赛必会）

例题：求$\sum _{i=1}^n\sum _{j=1}^n[gcd(i,j)=1]$（即$n\times n$网格中互质点对数量）。

解法思路（利用反演把“等于1”换成“求和”）：

1. 利用性质$[gcd(i,j)=1]=\sum _{d|gcd(i,j)}\mu (d)$。
2. 交换求和次序：

$$\sum _{i=1}^n\sum _{j=1}^n\sum _{d|i,d|j}\mu (d)=\sum _{d=1}^n\mu (d){\lfloor \frac{n}{d}\rfloor }^2$$

1. 配合整除分块（数论分块）即可在$O(\sqrt{n})$时间内算出。

---

第五部分：高级技巧 —— 杜教筛（快速求前缀和）

莫比乌斯反演结合狄利克雷卷积，可以构造出亚线性时间的数论函数前缀和算法（杜教筛）。

原理：设要求$S(n)=\sum _{i=1}^{n}f(i)$。
若能找到另一个函数$g$，使得$f\ast g=h$，且$h$的前缀和很好算，$g$的前缀和也很好算，则：

$$g(1)S(n)=\sum _{i=1}^n(f\ast g)(i)-\sum _{i=2}^{n}g(i)\cdot S\left(\lfloor \frac{n}{i}\rfloor \right)$$

利用这个递归式，可以快速求出$S(n)$。

例如：求$\sum _{i=1}^n\mu (i)$。
取$f=\mu ,g=\mathbf{1}$，则$h=\mu \ast \mathbf{1}=ϵ$。前缀和$\sum ϵ=1$很好算，直接代入即可。

---

总结对照表（速查）

概念	表达式	备注
卷积定义	$(f\ast g)(n)=\sum _{d|n}f(d)g(n/d)$	遍历因子
单位元	$ϵ(n)=[n=1]$	卷积中的“1”
莫比乌斯逆元	$\mu \ast \mathbf{1}=ϵ$	最重要公式
欧拉恒等式	$\phi \ast \mathbf{1}=\text{Id}$	推出$\phi =\text{Id}\ast \mu$
反演(约数)	$F=f\ast \mathbf{1}⟺f=F\ast \mu$	互推灵魂
常见套路	$[gcd(i,j)=1]=\sum _{d|gcd(i,j)}\mu (d)$	将条件转换成求和

---

如果你正在准备竞赛或刷题，这三个易错点请额外注意：

1. 下标起始：卷积中的$d$是正因子，必须从 1 到$n$。
2. 积性函数的卷积：两个积性函数的卷积仍是积性函数，利用这一点可以在线性筛（欧拉筛）中$O(n)$预处理$\mu ,\phi$等函数。
3. 边界条件：$\mu (1)=1$，计算反演时千万不要把$n=1$的情况漏掉。

如果你需要，我可以手写推演一遍杜教筛的完整步骤，或者给你三道难度递增的卷积练习题。你告诉我接下来想看哪个？

欧拉函数$\phi$

$\phi (n)=\sum _{i=1}^n[gcd(i,n)=1]$

方法一：组合计数法（最美妙的视角）

我们考虑 $n$个分数：

$$\frac{1}{n},\frac{2}{n},\frac{3}{n},\cdots ,\frac{n}{n}$$

显然，这串分数一共有 $n$ 个。

接下来，我们把这$n$个分数全部约分到最简形式。设约分后的分母为$d$，那么$d$一定是$n$的约数（因为分母是分子分母除以最大公约数得来的）。

关键来了：对于每一个固定的分母$d\mid n$，有多少个分数约分后恰好等于$\frac{?}{d}$（分子与$d$互质）呢？

• 分母为$d$的最简真分数（或等于1的分数）形式为$\frac{a}{d}$，其中必须满足$gcd(a,d)=1$。
• 同时，因为原分数的分母是$n$，分子是从$1$到$n$，所以$a$的取值范围恰好是$1\le a\le d$。

而$1$到$d$中与$d$互质的整数个数，正是欧拉函数的定义：$\phi (d)$。

总结计数：

• 左边（按分母分类）：$\sum _{d|n}\phi (d)$
• 右边（分数的总个数）：$n$

因此：

$$\sum _{d|n}\phi (d)=n$$

用卷积语言写，就是$\phi \ast \mathbf{1}=\text{Id}$。

---

方法二：积性函数证明（最严谨的代数法）

如果你对“积性函数”敏感，这个证明极其干脆：

1. 先证明$F(n)=\sum _{d|n}\phi (d)$是积性函数。
   因为$\phi$是积性函数，而“约数和”运算（即卷上$\mathbf{1}$）保持积性，所以$F(n)$也是积性函数。

2. 只需考察$n$的单一质因数幂$p^k$的情况：

$$F(p^k)=\sum _{d|p^k}\phi (d)=\phi (1)+\phi (p)+\phi (p^2)+\cdots +\phi (p^k)$$

代入欧拉函数在质数幂处的取值（$\phi (p^i)=p^i-p^{i-1}$）：

$$F(p^k)=1+(p-1)+(p^2-p)+(p^3-p^2)+\cdots +(p^k-p^{k-1})$$

这是一个望远镜求和（裂项相消），中间项全部抵消，只剩下：

$$F(p^k)=p^k$$

1. 推广到一般$n$：
   若$n=\prod p_i^{k_i}$，由于积性：

$$F(n)=\prod F(p_i^{k_i})=\prod p_i^{k_i}=n$$

证毕。

---

结合你刚学的莫比乌斯反演来反推验证

既然你刚学了莫比乌斯反演，我们可以用这个恒等式反推出欧拉函数的另一个表达式。

由$\phi \ast \mathbf{1}=\text{Id}$，两边同时卷上$\mu$（因为$\mathbf{1}$的逆是$\mu$）：

$$\phi \ast \mathbf{1}\ast \mu =\text{Id}\ast \mu$$

左边：$\phi \ast (\mathbf{1}\ast \mu )=\phi \ast ϵ=\phi$ 右边：$\text{Id}\ast \mu$

于是得到著名的欧拉反演公式：

$$\phi (n)=\sum _{d|n}\mu (d)\cdot \frac{n}{d}=n\sum _{d|n}\frac{\mu (d)}{d}$$

（例如：$\phi (6)=6\times (1-\frac{1}{2}-\frac{1}{3}+\frac{1}{6})=2$，完全正确。）

---

记忆小窍门（几何直观）

你可以把这个等式想象成：把$n$个格子按“周期”分组。分母$d$是$n$的周期，$\phi (d)$是在该周期下“新出现”的不可约位置，所有周期的不可约位置加起来，正好铺满$n$个整数点。这就是为什么$\sum _{d|n}\phi (d)=n$。

如果你对这个“分数约分”的证明还有疑问，或者想看我把它用在具体的竞赛题（比如求$\sum _{i=1}^{n}gcd(i,n)$）中，随时告诉我！

针对你这个二维求和 $\sum _{i=1}^m\sum _{j=1}^n[gcd(i,j)=1]$，直接套用莫比乌斯反演的核心套路，可以一步写出化简公式。

这个式子的几何意义是：在 $m\times n$ 的矩形网格点阵中，从原点 $(0,0)$ 出发能直接“看到”（即视线不被遮挡）的整点个数。

---

1. 反演化简（标准推导）

利用我们刚学的恒等式：$[gcd(i,j)=1]=\sum _{d\mid gcd(i,j)}\mu (d)$。

代入原式并交换求和次序（$d$ 必须同时整除 $i$ 和 $j$）：

$$\begin{array}{rl}\sum _{i=1}^m\sum _{j=1}^n[gcd(i,j)=1]& =\sum _{i=1}^m\sum _{j=1}^n\sum _{d\mid i,d\mid j}\mu (d)\\ & =\sum _{d=1}^{min(m,n)}\mu (d)\sum _{i=1,d\mid i}^m\sum _{j=1,d\mid j}^{n}1\end{array}$$

在 $1$ 到 $m$ 中，能被 $d$ 整除的数的个数为 $\lfloor \frac{m}{d}\rfloor$，同理 $j$ 有 $\lfloor \frac{n}{d}\rfloor$ 个。

最终公式：

$$\boxed{{\displaystyle \sum _{i=1}^m\sum _{j=1}^n[gcd(i,j)=1]=\sum _{d=1}^{min(m,n)}\mu (d)\lfloor \frac{m}{d}\rfloor \lfloor \frac{n}{d}\rfloor }}$$

---

2. 特殊情况：当 $m=n$（正方形网格）

如果 $m=n=N$，公式退化为：

$$\sum _{d=1}^N\mu (d){\lfloor \frac{N}{d}\rfloor }^2$$

这个结果还有一个极其优美的欧拉函数等价形式（利用我们刚证的 $\sum _{d|k}\phi (d)=k$）：

$$\sum _{i=1}^N\sum _{j=1}^N[gcd(i,j)=1]=1+2\sum _{i=1}^N\phi (i)$$

（其中的 $+1$ 是因为坐标 $(1,1)$ 在对角线交点处被重复计算，或者理解为只算一次原点视线）。

---

3. 如何快速计算？（数论分块 / 整除分块）

如果你需要编程计算（比如 $m,n\le {10}^{12}$），不能直接枚举 $d$，必须使用整除分块。

核心观察：随着 $d$ 增大，$\lfloor \frac{m}{d}\rfloor$ 和 $\lfloor \frac{n}{d}\rfloor$ 都会分段保持不变。我们可以将 $d$ 分成若干个区间 $[l,r]$，在同一个区间内这两个值不变。

计算步骤：

1. 预处理莫比乌斯函数的前缀和 $M(x)=\sum _{i=1}^x\mu (i)$（用线性筛）。
2. 设 $N=min(m,n)$。
3. 令 $l=1$，当 $l\le N$ 时：
   • 计算当前块的值：$v_m=\lfloor m/l\rfloor$，$v_n=\lfloor n/l\rfloor$
   • 计算块的右端点：$r=min(\lfloor \frac{m}{v_m}\rfloor ,\lfloor \frac{n}{v_n}\rfloor ,N)$
   • 这个区间 $[l,r]$ 的贡献为：$(M(r)-M(l-1))\times v_m\times v_n$
   • 令 $l=r+1$ 继续下一块。

复杂度：$O(\sqrt{m}+\sqrt{n})$，极快。

---

4. 举个具体例子（手算验证）

求 $m=4,n=6$ 时的值。

先列 $\mu (d)$：$\mu (1)=1,\mu (2)=-1,\mu (3)=-1,\mu (4)=0$。
代入公式：

$$d=1:1\times 4\times 6=24$$$$d=2:(-1)\times 2\times 3=-6$$$$d=3:(-1)\times 1\times 2=-2$$$$d=4:0\times 1\times 1=0$$

总和：$24-6-2=16$。

意义：在 $4\times 6$ 的网格中，有 $16$ 个点与原点连线不经过其他格点。

---

5. 与狄利克雷卷积的深层联系（拔高）

如果你把这个问题看成矩阵 $A_{i,j}=[gcd(i,j)=1]$，那么这个二维求和本质上是在对积性函数的二维前缀和做处理。

我们可以用狄利克雷卷积的语言重新包装： 设 $F(n,m)=\sum _{i=1}^m\sum _{j=1}^n[gcd(i,j)=1]$。 其实这就是把恒等函数 $\mathbf{1}$ 在二维格点上的卷积逆（即 $\mu$）做了个加权平均。这为以后学习多维莫比乌斯反演（如 $gcd$ 矩阵的行列式）打下了基础。

---

如果你需要，我可以直接给你一份C++ 整除分块的完整可运行代码，或者继续推导 三维情况 $\sum _{i=1}^a\sum _{j=1}^b\sum _{k=1}^c[gcd(i,j,k)=1]$ 的公式（套路完全一样，只是多乘一个下取整）。你告诉我下一步想看哪个？

数论分块/整除分块

TODO

FWT & 高位前缀和

TODO