莫比乌斯反演学习笔记
快速数论变换
·
·
算法·理论
前言
2025/8/26 upd：修正了几处错误。
莫比乌斯反演，是一种使用莫比乌斯函数进行容斥，对原本复杂的数学式子进行推导，使其运算能够更快速的数学方法，在 NOI 大纲中被评为 9 级算法，但实际上并不是特别难。
但由于作者本人在学习莫反时走过许多弯路，同时为了纪念作者学会了莫比乌斯反演，所以写了这篇文章，希望对大家有所帮助！
请保证你在阅读本文前有一定的数论与高中数学基础。
莫比乌斯函数
想要学会莫反（莫比乌斯反演的简称），首先要知道莫比乌斯函数。它的定义域为 \N^*，其定义如下：
将 n 质因数分解，得 n=\prod\limits_{i=1}^m\normalsize p_i^{c_i}，则 \mu(n)=\begin{cases}0&\exists\ i\in[1,m],c_i>1\\1&2\mid m,\forall\ i\in[1,m],c_i=1\\-1&2\nmid m,\forall\ i\in[1,m],c_i=1\end{cases}。
特别的，有 \mu(1)=1。
你可能会被这一坨式子吓坏，但没关系，接下来会详细讲解莫比乌斯函数。
首先看 \mu(n)=0 的情况。它的意思是说：有一个质因子，在 n 的质因数分解中出现了 2 次及以上，则说明 n 有平方因子。例如 4，其质因数分解为 2\times2，注意到 2 出现了两次，于是 4 内有平方因子，所以 \mu(4)=0。
再看 \mu(n)=1 的情况。它是在说如果 n 内不存在平方因子，且质因数分解后 n 的质因数有偶数个，则 \mu(n)=1。例如 6，质因数分解后为 2\times3，不存在平方因子，且有偶数个质因子，所以 \mu(6)=1。
最后看 \mu(n)=-1 的情况。其实与 \mu(n)=1 的情况相似，同样没有平方因子，但质因子有奇数个。例如 30，分解后得 2\times3\times5，不存在平方因子，且有奇数个质因子，所以 \mu(30)=-1；另外，所有质数的莫比乌斯函数值都为 -1，因为很显然，它们被分解后还是他们自身，质因子数量为 1，所以其莫比乌斯函数值都为 -1。
其有一个重要的性质：\sum\limits_{d|n}\mu(d)=[n=1]。
数论函数与狄利克雷卷积
数论函数
首先，你要知道什么是数论函数。
数论函数定义如下：
数论函数是定义域为 \N^*，值域为 \mathbb{C} 的子集的函数。
显然，上面提到的莫比乌斯函数就是一个数论函数，其定义域为 \N^*，值域为 \{-1,0,1\}。
还有一些其他常见的数论函数：
-
-
- $\sigma_k(n)=\sum\limits_{d|n}d^k$。
另外，还有一些函数可以用来充作数论函数：
-
- $\operatorname{id}(n)$：$k=1$ 时特殊情况。
-
-
狄利克雷卷积
其定义如下：
对于两个数论函数 f(n),g(n)，令它们的狄利克雷卷积结果为 (f*g)(n)，则 (f*g)(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})。
于是 \epsilon(n) 就成为了狄利克雷卷积的单位元，你可以用它和其他数论函数卷一下试试。
常见的狄利克雷卷积公式（一定要记牢了，不然忘了公式你会被创飞的！）：
-
\varphi*1=\operatorname{id}
-
\mu*1=\epsilon
-
1*1=d
-
1*\operatorname{id}_k=\sigma_k
-
莫比乌斯反演与欧拉反演
莫比乌斯反演
说了那么多，是时候进入正题了。
莫比乌斯反演的原理其实就一句话：
g(n)=\sum_{d|n}f(d)\Longleftrightarrow f(n)=\sum_{d|n}\mu(\frac{n}{d})g(d)
但是光知道这玩意屁用没有，看见莫反题该不会还不会。于是，我将会用几道题让你慢慢学会莫反推式子的方法（只教推式子，不讲代码实现）。
例题 1 GCD SUM
\begin{aligned}
&\ \ \ \ \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^nd[\gcd(i,j)=d]\\
&=\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=d]\\
&=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1]\\
&=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k|i,k|j}\mu(k)\\
&=\sum_{d=1}^nd\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}1\\
&=\sum_{d=1}^nd\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{kd}\rfloor^2\\
&\ \ \ \ \ \ \ \ \ 令\ t=kd,则\\
原式&=\sum_{t=1}^n\sum_{d|t}d\mu(\frac{t}{d})\lfloor\frac{n}{t}\rfloor^2\\
&=\sum_{t=1}^n\varphi(t)\lfloor\frac{n}{t}\rfloor^2
\end{aligned}
上面那个换元后换枚举顺序是一个很套路的方法，这样你能够将原来的式子写成狄利克雷卷积形式，在很多题目上都能方便处理，但你只要不会，你就会被卡死在那上面。（作者就因为这东西挂了好几次）
例题 2 [POI 2007] ZAP-Queries
以下默认 a\le b。
\begin{aligned}
&\ \ \sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=d]\\
&\ 令\ n=\lfloor\frac{a}{d}\rfloor,m=\lfloor\frac{b}{d}\rfloor,则\\
原式&=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{t|i,t|j}\mu(t)\\
&=\sum_{t=1}^{n}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}1\\
&=\sum_{t=1}^n\mu(t)\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor
\end{aligned}
例题 3 简单的数学题
\begin{aligned}
&\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^nij\sum_{d=1}^nd[\gcd(i,j)=d]\\
&=\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^nij[\gcd(i,j)=d]\\
&=\sum_{i=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[\gcd(i,j)=1]\\
&=\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij\sum_{k|i,k|j}\mu(k)\\
&=\sum_{d=1}^nd^3\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}k^2\mu(k)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}ij\\
&\ \ \ \ \ \ \ \ \ \ \ \ \ 令\ t=kd,则\\
原式&=\sum_{t=1}^n\sum_{d|t}d^3\mu(\frac{t}{d})(\frac{t}{d})^2\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{t}\rfloor}j\\
&=\sum_{t=1}^nt^2\varphi(t)\left(\frac{\lfloor\frac{n}{t}\rfloor(\lfloor\frac{n}{t}\rfloor+1)}{2}\right)^2
\end{aligned}
欧拉反演
欧拉反演相较于莫反而言，省去了大量的推导步骤，更加直接，但同样可以由莫反推出。
欧拉反演还是一句话：
n=\sum_{d|n}\varphi(d)
同样，只有这一句话同样也是屁用没有，接下来还是拿真题练练手。
例题 1 GCD SUM
\begin{aligned}
&\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,d|j}\varphi(d)\\
&=\sum_{d=1}^n\varphi(d)\sum_{d|i,i\le n}\sum_{d|j,j\le n}1\\
&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}1\\
&=\sum_{d=1}^n\varphi(d)\lfloor\frac{n}{d}\rfloor^2
\end{aligned}
怎么样，是不是感觉比莫反简单多了？
例题 2 简单的数学题
\begin{aligned}
&\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^nij\sum_{d|i,d|j}\varphi(d)\\
&=\sum_{d=1}^n\varphi(d)\sum_{d|i,i\le n}\sum_{d|j,j\le n}ij\\
&=\sum_{d=1}^nd^2\varphi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j\\
&=\sum_{d=1}^nd^2\varphi(d)\left(\frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2}\right)^2
\end{aligned}
后记
感谢 @Iniaugoty，@Rain_chr 与 @MarsCheng 三位大佬的指点，使我彻底学会了莫反。希望看到这里的各位能给他们三位关注，同时我也在这里无耻求关求赞。