莫比乌斯反演
莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$，如果很难直接求出它的值，而容易求出 $g(n)=\sum\limits_{d|n}f(d)$ 或 $h(n)=\sum\limits_{n|d}f(d)$，那么可以通过莫比乌斯反演简化运算，求得 $f(n)$ 的值。
莫比乌斯变换
形式 1
如果有 $f(n)=\sum\limits_{d|n}g(d)$，那么有 $g(n)=\sum\limits_{d|n}\mu(\frac{n}{d})f(d)$。
证明
$$\because f(n)=\sum\limits_{d|n}g(d)$$
$$\therefore f=g*1$$
$$\therefore f*\mu=g*1*\mu$$
$$\therefore f*\mu=g*\varepsilon$$
$$\therefore f*\mu=g$$
$$\therefore g(n)=\sum\limits_{d|n}f(d)\mu(\frac{n}{d})$$
解释
这种形式下，数论函数 $f(n)$ 称为数论函数 $g(n)$ 的莫比乌斯变换，数论函数 $g(n)$ 称为 $f(n)$ 的莫比乌斯逆变换（反演）。
形式 2
如果有 $f(n)=\sum\limits_{n|d}g(d)$，那么有 $g(n)=\sum\limits_{n|d}\mu(\frac{d}{n})f(d)$。
证明
考虑逆推，设 $d=kn$。
$$\begin{aligned} \sum\limits_{n|d}\mu(\frac{d}{n})f(d) &= \sum\limits_{k=1}^{+\infty}\mu(k)f(kn) \\ &= \sum\limits_{k=1}^{+\infty}\mu(k)\sum\limits_{kn|d}g(d) \\ &= \sum\limits_{n|d}g(d)\sum\limits_{k|\frac{d}{n}}\mu(k) \\ &= \sum\limits_{n|d}g(d)\varepsilon(\frac{d}{n}) \\ &= g(n) \end{aligned}$$
变形
如果有 $f(n)=\sum\limits_{d=1}^{\lfloor \frac{N}{n} \rfloor}g(d \times n)$，那么有 $g(n)=\sum\limits_{d=1}^{\lfloor \frac{N}{n} \rfloor}f(d \times n)\mu(d)$。
例题
| 名称 | 编号 | 备注 | 题解 |
|---|---|---|---|
| $\sum\limits_{x=1}^a\sum\limits_{y=1}^b[\gcd(x,y)=k]$ | |||
| $\sum\limits_{x=a}^b\sum\limits_{y=c}^d[\gcd(x,y)=k]$ | |||
| $\sum\limits_{k \mathrm{是质数}}\sum\limits_{x=1}^n\sum\limits_{y=1}^n[\gcd(x,y)=k]$ | |||
| $\sum\limits_{k \mathrm{是质数}}\sum\limits_{x=1}^n\sum\limits_{y=1}^m[\gcd(x,y)=k]$ | |||
| $\sum\limits_{i=1}^a\sum\limits_{j=1}^b\sum\limits_{k=1}^c[\gcd(i,j)=1][\gcd(j,k)=1][\gcd(k,i)=1]$ | |||
| $\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(i,j)$ | |||
| $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)$ | |||
| $\sum\limits_{i=1}^n \gcd(i,n)$，展开 $\varphi$ 函数 | |||
| $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{d}(ij)$，除数函数 $\operatorname{d}$ 的性质，整除分块 | |||
| $(\sum\limits_{i=1}^A\sum\limits_{j=1}^B\sum\limits_{k=1}^C\operatorname{d}(ijk)) \bmod (10^9+7)$，三元环计数 | |||
| $(\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\operatorname{lcm}(a_i,a_j)) \bmod 998244353$，莫比乌斯反演，狄利克雷后缀和 | |||
| $\sum\limits_{i=1}^n\operatorname{lcm}(i,n)$，套路同上一题 | |||
| 求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(F_i,F_j)$，其中 $F_k$ 表示斐波那契数列的第 $k$ 项 | |||
| 求 $f(n)=\sum\limits_{d|n}|\mu(d)|$，莫比乌斯反演 | |||
| 求 $f(n)=\sum\limits_{1 \le a<b \le n}[\gcd(a,b)=1][a+b \ge n]\dfrac{1}{ab}$，容斥原理，莫比乌斯反演 | |||
| Product | Luogu P5221 |