莫比乌斯反演总结
Dexterha
·
2026-01-18 19:19:21
·
算法·理论
莫比乌斯×狄利克雷
很早以前的总结了……\
今天比较特别，发表纪念一下。
前情提要
需要掌握
大型运算符交换顺序。
引入
定义
对此定义 $\mu(n)=\begin{cases}0&n 含平方因子\\(-1)^q&otherwise\end{cases}$。
定义元函数 \epsilon(n)=[n=1]=\begin{cases}1&n=1\\0&n\not=1\end{cases} 。
### 公式
积性函数
若 \gcd(x,y)=1 时，有 f(xy)=f(x)f(y) ，则称 f 是一个积性函数，\
若 f,g 为积性函数，则 h(i)=f(i)g(i) 也为积性函数（不同于狄利克雷卷积）。
积性函数的线性递推
若函数 f 为积性函数，那么一定可以按下面的方法转移。\
设 P(n) 为 n 中最小质因子，A(n) 为 n 中最小质因子的次数，定义 \mathrm{PA}(n)=P(n)^{A(n)} ：
f(n)=\begin{cases}1&n=1\\g(n)&n\not=1 \land n=\mathrm{PA}(n)\\f(\mathrm{PA}(n))f({n\over \mathrm{PA}(n)})&n\not=1 \land n\not=\mathrm{PA}(n)\end{cases}
这时，我们只需要处理 g(n) 即可， \
其余可以用线性筛（欧拉筛）来 O(n) 解决！
简介
莫比乌斯
莫比乌斯函数
\mu(x)
简洁的容斥系数，适用于：倍数容斥。
莫比乌斯反演
T(f)(n)=\sum_{d|n} f(d),R(f)(n)=\sum_{d|n} \mu\left({n\over d}\right) f(d)
用于化简式子（不常直接用）。
莫比乌斯的性质
\epsilon(x)=\sum_{d|x} \mu(d)
用于化简式子（常用）。
证明：\
设 n=\prod\limits_{i=1}^qp_i^{a_i} ，而 \mu(d)\not=0 的 d 当且仅当他的质因子指数 \leq 1 ， \
所以 n 的每个质因子都有两种取法，而 \mu(d) 就是(-1)^{指数取 1 的个数} ， \
根据二项式定理，当 n>1 时，奇数项的系数等于偶数项的系数，因此得证。
狄利克雷
狄利克雷卷积
h=f*g\Leftrightarrow h(x)=\sum_{d|x} f(d)g\left({x\over d}\right)
若 f,g 为积性函数，则 h 为积性函数。
狄利克雷卷积的性质
做以下定义：
\mathrm{Id}_k(x)=x^k
有性质：
交换律：f*g=g*f 。
结合律：(f*g)*h=f*(g*h) 。
分配率：f*(g+h)=f*g+f*h 。
单位元：\epsilon*f=f 。
逆元：若 f*g=\epsilon ，那么称 f 和 g 互为逆元，即 f=g^{-1},g=f^{-1} 。
若 f 和 g 为积性函数，则 f*g 也为积性函数，f^{-1} 也是积性函数。
若 f*g=h ，则 \mathrm{Id}_kf*\mathrm{Id}_kg=\mathrm{Id}_kh 。\
证明如下：
\begin{aligned}&\mathrm{Id}_kf*\mathrm{Id}_kg(n)\\=&\sum\limits_{d|n} f(d)g({n\over d})\mathrm{Id}_k(d)\mathrm{Id}_k({n\over d})\\=&\sum\limits_{d|n} f(d)g({n\over d})\mathrm{Id}_k(d{n\over d})\\=&\mathrm{Id}_k(n)\sum\limits_{d|n} f(d)g({n\over d})\\=&\mathrm{Id}_k(n)h(n)\end{aligned}
特别地，当 h(n)=\sum\limits_{d|n}f(d)g(d) ，若 f 和 g 为积性函数，h 也为积性函数，证明如下：\
设 c(d)=f(d)g(d) ，因为 f 和 g 为积性函数，所以直积后仍为积性函数， \
而 h(n)=\sum\limits_{d|n}c(d)=c*\mathrm{Id}_0 ，所以 h 也为积性函数。
莫比乌斯×狄利克雷
这里对于函数 f 定义：
T(f)=f*\mathrm{Id}_0,R(f)=f*\mu
满足：
T(R(f))=R(T(f))=f
常见形式与例子
看不懂的，配套下文的技巧观看。
模板 1 ：函数套 \gcd
关于形如 \sum_{i=1}^{n} \sum_{j=1}^{m} f\left(\gcd\left(i,j\right)\right) 的模板解法：
\begin{aligned}
&\sum_{i=1}^{n} \sum_{j=1}^{m} f\left(\gcd\left(i,j\right)\right)
& 原式\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor}
\sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor}\left[\gcd\left(i,j\right)=1\right]
& 枚举 \gcd 的结果 d\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor}
\sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor}
\sum_{k|i\land k|j} \mu\left(k\right)
& 莫比乌斯函数的性质\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right)
\sum_{i=1}^{\left\lfloor {n\over kd}\right\rfloor}
\sum_{j=1}^{\left\lfloor {m\over kd}\right\rfloor} 1
& 交换大型运算符位置\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right)
\left\lfloor {n\over kd}\right\rfloor
\left\lfloor {m\over kd}\right\rfloor
& 易得\\
=&\sum_{t=1}^{\min\left\{n,m\right\}}
\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)
\left\lfloor {n\over t}\right\rfloor
\left\lfloor {m\over t}\right\rfloor
& 换元令 t=kd\\
=&\sum_{t=1}^{\min\left\{n,m\right\}}
\left\lfloor {n\over t}\right\rfloor
\left\lfloor {m\over t}\right\rfloor
\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)
\end{aligned}
还没有结束，最后一步是尝试证明 g(t)=\sum\limits_{k|t}f\left({t\over k}\right)\mu\left(k\right) 是一个积性函数。 \
（这是狄利克雷卷积，可以只证明 f 的积性，得到 g 的积性）
无论是否证得 g 是否具有积性， \
只要可以快速预处理 g 即可。
然后求 g 的前缀和 s(t)=\sum\limits_{i=1}^{t} g(i) ， \
求答案使用整数分块。
例题： \
对于 n,m \le 10^7 ，T \le 10^4 。求有多少对正整数 (x,y) 满足 x \le n \wedge y \le m ，使得 \gcd(x,y) 是一个质数。
模板 2 ：函数乘函数乘函数套 \gcd
关于形如 \sum_{i=1}^{n} \sum_{j=1}^{m} g(i)h(j)f\left(\gcd\left(i,j\right)\right) 的模板解法：
\begin{aligned}
&\sum_{i=1}^{n} \sum_{j=1}^{m} g(i)h(j)f\left(\gcd\left(i,j\right)\right)
& 原式\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor} g(i)
\sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor} h(j)
\left[\gcd\left(i,j\right)=1\right]
& 枚举 \gcd 的结果 d\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor}g(i)
\sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor}h(j)
\sum_{k|i\land k|j} \mu\left(k\right)
& 莫比乌斯函数的性质\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right)
\sum_{i=1}^{\left\lfloor {n\over kd}\right\rfloor} h(i)
\sum_{j=1}^{\left\lfloor {m\over kd}\right\rfloor} g(j)
& 交换大型运算符位置\\
=&\sum_{t=1}^{\min\left\{n,m\right\}}
\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)
\sum_{i=1}^{\left\lfloor {n\over t}\right\rfloor} h(i)
\sum_{j=1}^{\left\lfloor {m\over t}\right\rfloor} g(j)
& 换元令 t=kd\\
=&\sum_{t=1}^{\min\left\{n,m\right\}}
\sum_{i=1}^{\left\lfloor {n\over t}\right\rfloor} h(i)
\sum_{j=1}^{\left\lfloor {m\over t}\right\rfloor} g(j)
\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)
\end{aligned}
后三个求和只有公共项 t ，可以按 t 分别预处理。
例题：
对于 T \le 10^4 ，n,m \le 10^7 ，求：
\sum_{i=1}^n{\sum_{j=1}^{m}\mathrm{lcm}(i,j)}
模板 3 ：多要求
\color{purple}{终极模板：见招拆招}
关于形如 \sum\limits_{\forall i\in[1..n],1\le b_i \le a_i} f(\gcd\limits_{k\in[1..n]} b_k) \prod\limits_{j=1}^{n} g_j(b_j) 的模板解法， \
这并不好直接表示出来，但是推法几乎一样。 \
所以，只给出结论：
\begin{aligned}
\sum_{t=1}^{\min\limits_{l=1}^{n}{a_l}}\left(\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)\right)\prod\limits_{p=1}^{n}\sum_{i=1}^{\left\lfloor {a_p\over t} \right\rfloor} g_p(i)
\end{aligned}
模板 4 ：\gcd 乘积
关于形如 \prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f(\gcd(i,j)) 的暴力解（不使用 \ln 与 \exp ）模板：
\begin{aligned}
&\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f(\gcd(i,j))\\
=&\prod_{d=1}^{\min\{n,m\}}
f(d)^{
\sum\limits_{i=1}^{\left\lfloor{n\over d}\right\rfloor}
\sum\limits_{j=1}^{\left\lfloor{m\over d}\right\rfloor}
[\gcd(i,j)=1]
}\\
=&\prod_{d=1}^{\min\{n,m\}}
f(d)^{
\sum\limits_{i=1}^{\left\lfloor{n\over d}\right\rfloor}
\sum\limits_{j=1}^{\left\lfloor{m\over d}\right\rfloor}
\sum\limits_{k|i\land k|j} \mu(k)
}\\
=&\prod_{d=1}^{\min\{n,m\}}
f(d)^{
\sum\limits_{k=1}^{\min\left\{
\left\lfloor{n\over d}\right\rfloor
\left\lfloor{m\over d}\right\rfloor
\right\}} \mu(k)
\left\lfloor{n\over kd}\right\rfloor
\left\lfloor{m\over kd}\right\rfloor
}\\
=&
\prod_{t=1}^{\min\{n,m\}}
\prod_{d|t}
f(d)^{
\mu({t\over d})
\left\lfloor{n\over t}\right\rfloor
\left\lfloor{m\over t}\right\rfloor
}\\
=&
\prod_{t=1}^{\min\{n,m\}}
\left(\prod_{d|t}
f(d)^{
\mu({t\over d})
}\right)
^{
\left\lfloor{n\over t}\right\rfloor
\left\lfloor{m\over t}\right\rfloor
}
\end{aligned}
求解技巧
技巧 1 ：枚举答案
以模板 1 为例：
\begin{aligned}
&\sum_{i=1}^{n} \sum_{j=1}^{m} f\left(\gcd\left(i,j\right)\right)
\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{n}
\sum_{j=1}^{m}\left[\gcd\left(i,j\right)=d\right]\\
\end{aligned}
枚举 \gcd 的结果 d ，然后调整要求。
技巧 2 ：构造元函数
以模板 1 为例：
\begin{aligned}
&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{n}
\sum_{j=1}^{m}\left[\gcd\left(i,j\right)=d\right]\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i'=1}^{\left\lfloor {n\over d}\right\rfloor}
\sum_{j'=1}^{\left\lfloor {m\over d}\right\rfloor}\left[\gcd\left(i',j'\right)=1\right]\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor}
\sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor}
\sum_{k|i\land k|j} \mu\left(k\right)
\end{aligned}
考虑到，若 \gcd(i,j)=d ，那么 i,j 都是 d 的倍数，且 \gcd\left({i \over d},{j\over d}\right)={d\over d}=1 ， \
因此，直接枚举 d 的倍数。 \
换元 i'={i\over d},j'={j\over d} ， \
因此，i' 的上限就变为了 \left\lfloor {n\over d}\right\rfloor ，\gcd(i',j')=1 。 \
以约数个数和为例， \
设 $d(x)$ 表示 $x$ 的约数个数：
$$
\begin{aligned}
&\sum_{i=1}^n{\sum_{j=1}^{m}d(ij)}\\
=&\sum_{i=1}^n{\sum_{j=1}^{m}\sum_{u|i}{\sum_{v|j}{[\gcd(u,v)=1]}}}\\
=&\sum_{u=1}^n\sum_{v=1}^{m}[\gcd(u,v)=1]\sum_{u|i}\sum_{v|j}1\\
=&\sum_{u=1}^n\sum_{v=1}^{m}[\gcd(u,v)=1]\left\lfloor{n\over u}\right\rfloor\left\lfloor{m\over v}\right\rfloor\\
=&\sum_{u=1}^n\sum_{v=1}^{m}\left\lfloor{n\over u}\right\rfloor\left\lfloor{m\over v}\right\rfloor\sum_{d|i\land d|j}{\mu(d)}\\
\end{aligned}
$$
这里对 $d(ij)=\sum\limits_{u|i}{\sum\limits_{v|j}{[\gcd(u,v)=1]}}$ 不展开证明，感兴趣的可以自证。
### 技巧 $3$：交换大型运算符+换元
以模板 $1$ 为例：
$$
\begin{aligned}
&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{i=1}^{\left\lfloor {n\over d}\right\rfloor}
\sum_{j=1}^{\left\lfloor {m\over d}\right\rfloor}
\sum_{k|i\land k|j} \mu\left(k\right)\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right)
\sum_{i=1}^{\left\lfloor {n\over kd}\right\rfloor}
\sum_{j=1}^{\left\lfloor {m\over kd}\right\rfloor} 1\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}f(d)
\sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}\mu\left(k\right)
\left\lfloor {n\over kd}\right\rfloor
\left\lfloor {m\over kd}\right\rfloor\\
=&\sum_{d=1}^{\min\left\{n,m\right\}}
\sum_{k=1}^{\min\left\{\left\lfloor {n\over d}\right\rfloor,\left\lfloor {m\over d}\right\rfloor\right\}}f(d)\mu\left(k\right)
\left\lfloor {n\over kd}\right\rfloor
\left\lfloor {m\over kd}\right\rfloor\\
=&\sum_{t=1}^{\min\left\{n,m\right\}}
\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)
\left\lfloor {n\over t}\right\rfloor
\left\lfloor {m\over t}\right\rfloor\\
=&\sum_{t=1}^{\min\left\{n,m\right\}}
\left\lfloor {n\over t}\right\rfloor
\left\lfloor {m\over t}\right\rfloor
\sum_{k|t}f\left({t\over k}\right)\mu\left(k\right)
\end{aligned}
$$
将含 $\mu$ 的式子换到第二个，再令 $t=kd$，得到最终式子。
以约数个数和为例：
$$
\begin{aligned}
&\sum_{u=1}^n\sum_{v=1}^{m}\left\lfloor{n\over u}\right\rfloor\left\lfloor{m\over v}\right\rfloor\sum_{d|i\land d|j}{\mu(d)}\\
=&\sum_{d=1}^{\min\{n,m\}}{\mu(d)\sum_{d|i\land i\le n}{\left\lfloor {n\over i}\right\rfloor}\sum_{d|j\land j\le m}{\left\lfloor {m\over j}\right\rfloor}}\\
=&\sum_{d=1}^{\min\{n,m\}}{\mu(d)
\sum_{i=1}^{\left\lfloor{n\over d}\right\rfloor}{\left\lfloor {n\over id}\right\rfloor}
\sum_{j=1}^{\left\lfloor{m\over d}\right\rfloor}{\left\lfloor {m\over jd}\right\rfloor}
}\\
\end{aligned}
$$
### 技巧 $4$：快速预处理
运用狄利克雷卷积，推出积性： \
$f(x)=\sum\limits_{d|x} {x\over d}\mu(d)$ \
可以看作：$f=\mathrm{Id}_1 * \mu$， \
由于 $\mathrm{Id}_1,\mu$ 都是积函数， \
所以 $f$ 是积函数。
直接推出积性： \
$f(x)=\sum\limits_{d|x} d\mu(d)$ \
定义 $g(x)=x\mu(x)$， \
设 $a,b$ 满足 $\gcd(a,b)=1$， \
$g(ab)=ab\mu(ab)=a\mu(a)b\mu(b)=g(a)g(b)$， \
因此 $g$ 为积函数， \
又因为 $f=\mathrm{Id_0} * g$，所以 $f$ 也是积函数。
当然，不乏有棘手的式子难以转移， \
这类转移有时是题的难点， \
不妨打表得到结论反推证明。
### 技巧 $5$：换眼光看式子
以约数个数和为例：
$$
\begin{aligned}
&\sum_{d=1}^{\min\{n,m\}}{\mu(d)
\sum_{i=1}^{\left\lfloor{n\over d}\right\rfloor}{\left\lfloor {n\over id}\right\rfloor}
\sum_{j=1}^{\left\lfloor{m\over d}\right\rfloor}{\left\lfloor {m\over jd}\right\rfloor}
}\\
=&\sum_{d=1}^{\min\{n,m\}}{\mu(d)
\sum_{i=1}^{\left\lfloor{n\over d}\right\rfloor}{\left\lfloor {\left\lfloor{n\over d}\right\rfloor\over i}\right\rfloor}
\sum_{j=1}^{\left\lfloor{m\over d}\right\rfloor}{\left\lfloor {\left\lfloor{m\over d}\right\rfloor\over j}\right\rfloor}
}
\end{aligned}
$$
这种形式便于预处理：$f(x)=\sum\limits_{i=1}^{x} {\left\lfloor{x\over i}\right\rfloor}$。
### 技巧 $6$：无关项分别求解
在乘法的莫比乌斯反演中很可能出现， \
以幽灵乐团为例：
$$
\prod_{i=1}^{A}{\prod_{j=1}^{B}{\prod_{k=1}^{C}{\left(\frac{\mathrm{lcm}(i,j)}{\gcd(i,k)}\right)^\alpha}}}
$$
观察上式，可以将其拆为：
$$
{
\left(
\prod\limits_{i=1}^{A}
\prod\limits_{j=1}^{B}
\prod\limits_{k=1}^{C}
i^\alpha
\right)\left(
\prod\limits_{i=1}^{A}
\prod\limits_{j=1}^{B}
\prod\limits_{k=1}^{C}
j^\alpha
\right)
\over
\left(
\prod\limits_{i=1}^{A}
\prod\limits_{j=1}^{B}
\prod\limits_{k=1}^{C}
\gcd(i,j)^\alpha
\right)
\left(
\prod\limits_{i=1}^{A}
\prod\limits_{j=1}^{B}
\prod\limits_{k=1}^{C}
\gcd(i,k)^\alpha
\right)
}
$$
### 技巧 $7$：对数反演
（名字是乱起的） \
定义 $\ln(f)(x)=ln(f(x)),\exp(f)(x)=\exp(f(x))$， \
那么 $f=\exp(\ln(f))$， \
$\ln$ 可以让运算降级，方便计算。
### 技巧 $8$：积分估值
有时会出现双重整数分块： \
$\sum\limits_{i=1}^{n}\left\lfloor{n\over i}\right\rfloor\sum\limits_{j=1}^{\left\lfloor{n\over i}\right\rfloor} \left\lfloor{n\over j}\right\rfloor j$ \
这一式子计算的复杂度为 $\Theta(n^{3 \over 4})$，可以使用积分估值计算复杂度。