【学习笔记】极简的莫比乌斯反演

# Part 1 前置芝士
## 1.1 数论函数

数论函数：对于函数 $f$，若满足定义域为正整数，则称这个函数为 **数论函数**。

加性函数：对于函数 $f$ 若满足  $\gcd(p,q)=1(p,q \in \mathbb N^+)$ 时 $f(pq)=f(p)+f(q)$，则称函数 $f$ 为 **加性函数。**

积性函数：对于函数 $f$ 若满足 $\gcd(p,q)=1(p,q \in \mathbb N^+)$ 时 $f(pq)=f(p)f(q)$，则称函数 $f$ 为 **积性函数**。

若将值域扩大到任意 $p,q(p,q \in \mathbb N^+)$，仍然成立，则称为 **完全加性（或积性）函数**。

> 加性函数与积性函数均属于数论函数。
> tip：$\gcd(p,q)=1$ 指 $p,q$ 互质。
## 1.2 莫比乌斯函数

根据 贝尔级数 可得：
$$
\begin{array}{c}
\mu(p^k)=\begin{cases}1&k=0\\-1&k=1\\0&k>1\end{cases} \\

\therefore \mu(n)=\begin{cases}1&n=1\\(-1)^k&n=p_1p_2...p_k，p_i \ 为 \ n \ 的质因子且两两互质\\0&\text{otherwise}\end{cases}
\end{array}
$$
> tip：$\text{otherwise}$ 指不满足上述条件。

## 1.3 莫比乌斯函数性质

### 性质 1
我们注意到，莫比乌斯函数有一个 **重要性质**：
$$
\sum_{d|n}\mu(d)=[n=1]
$$
> tip：$d|n$ 表示能被 $n$ 整除的 $d$。$[n=1]$ 指 $n=1$ 则值为 $1$，否则为 $0$。

（口糊一下：对于所有能被 $n$ 整除的数，它们所有的莫比乌斯函数和，当 $n$ 等于 $1$ 时为 $1$，否则为 $0$）。

> *来自百度百科的证明*：
> 1. 当 $n=1$ 时易证。
> 2. 当 $n \ne 0$ 时，不妨令 $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}$。易证：在 $n$ 的所有因子中，莫比乌斯值不为 $0$ 的只有质因子次数为 $1$ 的因子，而质因子次数为 $a$ 的因子有 $C_k^r$ 个。$\therefore \sum\limits_{d|n} \mu(n)=C_k^0 - C_k^1 + C_k^2 +...+ (-1)^k C_k^k=\sum\limits_{i=0}^k(-1)^i C_k^i$   
### 性质 2 ？
就需要用到莫比乌斯反演了。
# Part 2 莫比乌斯反演
## 2.1 芝士：欧拉函数
直接看：
$$
\varphi(n)=\sum_{i=1}^{n}[(n,i)=1]
$$

可能没看懂，口糊一下，求所有不大于 $n$ 与 $n$ 互质的数。
那这有什么用？
再看一个重要性质：
$$
\sum_{d|n}\varphi(n)=n
$$
~~再口糊一下~~，所有能被 $n$ 整除的数的欧拉函数和为 $n$。
> *来自 OI wiki 的证明*：
> 如果 $\gcd(k,n)=d$，那么 $\gcd(\frac{k}{d},\frac{n}{d})=1,(k<n)$。
> 不妨设 $f(x)$ 表示 $\gcd{k,n}=x$ 的数的个数，那么 $n=\sum\limits_{i=1}^{n}f(i)$。
>   根据上面证明，我们注意到，$f(x)=\varphi(\frac{n}{x})$，从而 $n=\sum\limits_{d|n}\varphi(\frac{n}{d})$。再次注意到，约数 $d$ 和 $\frac{n}{d}$ 具有对称性，$\therefore n=\sum\limits_{d|n} \varphi (d)$。
## 2.2 莫比乌斯反演及其证明
有了欧拉函数的铺垫，接下来就简单了。
还是经典直接上公式：
$$
g(n)=\sum_{d|n} f(d)\Longleftrightarrow f(n)=\sum_{d|n}g(d)\mu \left (\frac{n}{d} \right)
$$
啊！！！完全看不懂怎么办。$g$ 和 $f$ 是什么呀？

别慌，$g$ 和 $f$ 只是两个数论函数，并没有定义什么。其实只是如果 $g(n)=\sum\limits_{d|n} f(d)$ 或 $f(n)=\sum\limits_{d|n}g(d)\mu \left (\frac{n}{d} \right)$ 中的一个条件满足，那么另一个条件也满足。
~~不过做题目时基本用不上~~。

它在做题目中最经典得运用就是这个，在下面例题中也经常用到：
$$
\sum_{p|\gcd(i,j)}\mu(p)=[\gcd(i,j)=1]
$$

接下来要正确性证明了，这里采用喜闻乐见的推柿子大法：
$$
g(n)=\sum_{d|n}g(d)\mu \left (\frac{n}{d} \right)=\sum_{d|n,t|\frac{n}{d}}g(t)\mu\left(\frac{n}{d}\right)=\sum_{t|n}g(t)\sum_{d|\frac{n}{d}}\mu(d)=g(n)
$$
## 2.3 性质 2

现在就知道了，$\sum\limits_{d|n}\frac{\mu (d)}{d} = \frac{\varphi (n)}{n}$，证明也十分简单。

令 $F(n)=n$，$f(n)=\varphi(n)$，直接代入莫比乌斯反演即可。

## 2.4 莫比乌斯反演经典例题

### Ex.1 [LuoguP3455 ZAP-Queries](https://www.luogu.com.cn/problem/P3455)
#### 题意简述
对 $T$ 组询问求 $\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=d]$。
数据范围：$1\le d \le a,b \le 5\times10^4$，$T\le 5\times 10^4$。
#### 解题思路
不妨令 $a\le b$。约去 $d$ 得：
$$
\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}[\gcd(i,j)=1]
$$

注意到，$\sum\limits_{p|n}\mu(n)=[n=1]$ 可以变为 $\sum\limits_{p|\gcd(i,j)}\mu(p)=[\gcd(i,j)=1]$，代入进去，得：
$$
\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\sum_{p|\gcd(i,j)}\mu{(p)}
$$
枚举 $p$，$\because p|\gcd(i,j)$，$\therefore p$ 为 $i,j$ 的因数：
$$
\therefore 原式=\sum_{p=1}^{\lfloor \frac {a}{d} \rfloor}\mu{(p)}   \times {\lfloor \frac{a}{dp} \rfloor}\times{\lfloor \frac{b}{dp} \rfloor}
$$
[整除分块（数论分块）](https://www.luogu.com.cn/article/a55ls8kg)求解即可。
### Ex.2 [LuoguP2257 YY的GCD](https://www.luogu.com.cn/problem/P2257)

#### 题意简述
对 $T$ 组询问求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j) \in prime]$。 
数据范围：$T=10^4，N,M\le10^7$。
#### 解题思路
我们不妨令 $n\le m$，$k$ 为质数，则 $k\le n$   
推一下柿子：
$$
\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j) \in prime]=\sum_{k=1}^{n}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k](k\in prime)
$$

~~太史了~~，同时约去 $k$ 一下，得：
$$
\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i,j)=1](k\in prime)
$$
注意到，$\sum\limits_{d|n}\mu(d)=[n=1]$ 可以变为 $\sum\limits_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1]$，代入进去，得：
$$
\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|\gcd(i,j)}\mu(d)(k\in prime)
$$
枚举 $d$，$\because d|\gcd(i,j)$，$\therefore d$ 为 $i,j$ 的因数：
$$
\therefore 原式=\sum_{k=1}^n\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\times\lfloor\frac{n}{kd}\rfloor\times\lfloor\frac{m}{kd}\rfloor(k \in prime)
$$
这下是不是好多了，但是，别急，不妨设 $T=kd$，则：
$$
原式=\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d)\times \lfloor
 \frac{n}{T}\rfloor\times \lfloor
 \frac{m}{T}\rfloor (k \in prime)$$
 枚举 $T$，得：
 $$
 \sum_{T=1}^n\lfloor \frac{n}{T}\rfloor\times\lfloor\frac{m}{T}\rfloor \sum_{k|T,k \in prime} \mu \left( \frac{T}{k} \right)
$$
预处理 $k$，整除分块即可做出。
### Ex.3 [LuoguP3327 约数个数和](https://www.luogu.com.cn/problem/P3327)
#### 题意简述

设 $d(x)$ 为 $x$ 的约数个数，给定 $T$ 组数据 $n,m$，求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)$。
数据范围：$1\le T,n,m \le 50000$。
#### 解题思路
不难发现：
$$
\begin{matrix}
d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] \\
\therefore \sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] 
\end{matrix}
$$

枚举 $i$ 和 $j$，不如直接枚举 $x$ 和 $y$，可得：
$$
\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor [\gcd(x,y)=1] 
$$
同样的道理：
$$

\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor  \sum\limits_{d|\gcd(x,y)}\mu(d)
$$
令 $n \le m$，得：
$$
\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor  \sum\limits_{d=1}^n\mu(d)\times[d|\gcd(x,y)]
$$
约去 $d$，得：
$$
\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{dx}\rfloor \lfloor \frac{m}{dy} \rfloor  \sum\limits_{d=1}^n\mu(d)
$$
再移项变好看一点，得：
$$
\sum\limits_{d=1}^n\mu(d) \left(\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor \frac{n}{dx}\rfloor\right)\left(\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor}  \lfloor \frac{m}{dy} \rfloor  \right)
$$
整除分块即可。
### Ex.4 [LuoguP1829 Crash的数字表格](https://www.luogu.com.cn/problem/P1829)
#### 题意简述
求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)$ 对 $20101009$ 取模的值。
> $\operatorname{lcm}(i,j)$ 指 $i$ 和 $j$ 的最小公倍数。

数据范围： $n,m\le 10^7$ （对 $20101009$ 取模）
#### 解题思路
令 $n\le m$，不难发现：
$$
\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)=\sum_{i=1}^n\sum_{j=1}^m\frac{i\cdot j}{\gcd(i,j)}=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{i\times j}{d} [\gcd(i,j)=d]
$$
约去 $d$，得：
$$
\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} {i\times j\times d}[\gcd(i,j)=1]
$$
还是同样的道理：
$$
原式=\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} {i\times j\times d}\sum\limits_{k|\gcd(i,j)}\mu(k)
$$
拆开来，再移项，得：
$$
\sum\limits_{d=1}^nd\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}i[\gcd(k,i)=1]\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}j[\gcd(k,j)=1]
$$
约去 $k$ 得：
$$
\sum\limits_{d=1}^nd\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{dk} \rfloor}ik\sum\limits_{j=1}^{\lfloor \frac{m}{dk} \rfloor}jk
$$
太丑了，化简一下：
$$
\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{dk} \rfloor}i\sum\limits_{j=1}^{\lfloor \frac{m}{dk} \rfloor}j
$$
根据等差数列求和公式：$S=\frac{(a_1+a_n)\times n}{2}$。再进行进一步拆开，得：
$$
\begin{align}
&\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\times \frac{\lfloor \frac{n}{dk} \rfloor(\lfloor \frac{n}{dk} \rfloor + 1)}{2}\times \frac{\lfloor \frac{m}{dk} \rfloor(\lfloor \frac{m}{dk} \rfloor + 1)}{2} \\
=&\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\times \frac{\lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor (\lfloor \frac{n}{dk} \rfloor + 1) (\lfloor \frac{m}{dk} \rfloor + 1)}{4}
\end{align}
$$
其实这样已经可以在洛谷 ~~卡过了~~。但是，显然这 $O(n^2)$ 解法还是不够优秀。
来，设 $x=dk$，所以：
$$
\begin{align}
原式&=\sum\limits_{x=1}^nx\sum\limits_{k|x}k\mu(k)\times \frac{\lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor (\lfloor \frac{n}{x} \rfloor + 1) (\lfloor \frac{m}{x} \rfloor + 1)}{4}
\end{align}
$$
令 $g(x)=\sum\limits_{d|x}xd \times \mu(d)$，注意到，函数 $g$ 是一个积性函数。
$$
\begin{align}
\therefore g\left(\prod P_i^{a_i}\right)&=\prod g\left(P_i^{a_{i}}\right)
\\ 
&=\prod\left(x\times P_{i^0}\times \mu(1) +x\times P_{i}\times\mu\left(P_i\right)  \right) \\
&=\prod\left((1-P_{i})x\right) \\
\end{align}
$$
$$
\begin{align}
\therefore &g(p)=1-p \\
&g(p^k)=g(p^{k-1}) \\
\therefore &g(np)=g(n)\times g(p),\left(\gcd(n,p)=1\right) 
\end{align}
$$
筛一下，就出来了
# Part 3 总结
这篇是本蒟蒻第一篇算法专栏，结合了 OI Wiki，百度百科与许多题解。其中特意没有写 [狄利克雷卷积](https://oi-wiki.org/math/poly/dgf/#dirichlet-%E5%8D%B7%E7%A7%AF)，意在更容易理解，有兴趣可以阅读。若有错误，欢迎指出。

莫比乌斯反演其实很简单，大部分只需用 $\sum\limits_{p|\gcd(i,j)}\mu(p)=[\gcd(i,j)=1]$ 这一公式，难在推柿子。它是数论中的重要部分，希望大家能熟练掌握。

正在渲染内容...