---
title: "数论"
---

## 狄利克雷卷积

### 第一部分：狄利克雷卷积（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