狄利克雷卷积

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

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

$(f* g)(n) = \sum_{d|n} f(d) \cdot g\left(\frac{n}{d}\right)$

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

1. 三大核心性质

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

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

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

$\epsilon(n) = \begin{cases} 1 & (n = 1) \\ 0 & (n > 1) \end{cases}$

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

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

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

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

1.$\varphi * \mathbf{1} = \text{Id}$ 即：$\sum_{d|n} \varphi(d) = n$

2.$\mu * \mathbf{1} = \epsilon$ 即：$\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{cases} 1 & (n = 1) \\ (-1)^k & (a_1 = a_2 = \dots = a_k = 1，\text{即无平方因子数}) \\ 0 & (\text{存在某个 } a_i \ge 2，\text{即含有平方因子}) \end{cases}

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

$\sum_{d|n} \mu(d) = \begin{cases} 1 & (n = 1) \\ 0 & (n > 1) \end{cases}$

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

---

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

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

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

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

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

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

即：$f = F * \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) \left\lfloor \frac{n}{d} \right\rfloor^2$

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

---

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

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

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

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

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

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

---

总结对照表（速查）

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

---

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

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

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

欧拉函数$\varphi$

$\varphi(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$互质的整数个数，正是欧拉函数的定义：$\varphi(d)$。

总结计数：

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

因此：

$\sum_{d|n} \varphi(d) = n$

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

---

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

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

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

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

$F(p^k) = \sum_{d|p^k} \varphi(d) = \varphi(1) + \varphi(p) + \varphi(p^2) + \cdots + \varphi(p^k)$

代入欧拉函数在质数幂处的取值（$\varphi(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$

证毕。

---

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

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

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

$\varphi* \mathbf{1} *\mu = \text{Id}* \mu$

左边：$\varphi *(\mathbf{1}* \mu) = \varphi *\epsilon = \varphi$ 右边：$\text{Id}* \mu$

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

$\varphi(n) = \sum_{d|n} \mu(d) \cdot \frac{n}{d} = n \sum_{d|n} \frac{\mu(d)}{d}$

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

---

记忆小窍门（几何直观）

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

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

最终公式：

\boxed{\sum_{i=1}^m \sum_{j=1}^n [\gcd(i, j)=1] = \sum_{d=1}^{\min(m, n)} \mu(d) \left\lfloor \frac{m}{d} \right\rfloor \left\lfloor \frac{n}{d} \right\rfloor}

---

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

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

$\sum_{d=1}^{N} \mu(d) \left\lfloor \frac{N}{d} \right\rfloor^2$

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

$\sum_{i=1}^N \sum_{j=1}^N [\gcd(i, j)=1] = 1 + 2\sum_{i=1}^N \varphi(i)$

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

---

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

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

核心观察：随着 $d$ 增大，$\left\lfloor \frac{m}{d} \right\rfloor$ 和 $\left\lfloor \frac{n}{d} \right\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\left( \left\lfloor \frac{m}{v_m} \right\rfloor,\ \left\lfloor \frac{n}{v_n} \right\rfloor, \ N \right)$
   • 这个区间 $[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