浅谈莫比乌斯反演

简介

最近经常演人/被人演,所以是时候学一学反演了。

莫比乌斯函数

定义

对于正整数 nn,若对其分解质因数有 n=p1c1p2c2pkck (ci>0)n = p_1^{c_1} p_2^{c_2} \dots p_k^{c_k} \ (c_i > 0),则:

μ(n)={1n=10ci>1(1)kotherwise\mu(n) =
\begin{cases}
1 & n = 1 \
0 & \exists c_i > 1 \
(-1)^k & \text{otherwise}
\end{cases}

通俗地来讲,当 n=1n = 1 时,μ(n)=1\mu(n) = 1;当 nn 的因子中存在完全平方数时,μ(n)=0\mu(n) = 0。对于剩余情况,也就是对 nn 质因数分解可得到 n=p1p2pkn = p_1p_2 \dots p_k 的情况,μ(n)=(1)k\mu(n) = (-1)^k,即 μ(n)\mu(n) 的值取决于 nn 不同质因数的个数。

性质

dnμ(d)={1n=10otherwise\sum\limits_{d \mid n} \mu(d) =
\begin{cases}
1 & n = 1\
0 & \text{otherwise} \
\end{cases}

下面给出简要证明:

  1. n=1n = 1 时,显然有 dnμ(d)=1\sum\limits_{d \mid n} \mu(d) = 1
  2. n1n \neq 1 时,有 k>0k > 0。记 n=p1c1p2c2pkck (ci>0)n = p_1{c_1}p_2{c_2} \dots p_k^{c_k} \ (c_i > 0)。对于 dnd \mid nμ(d)0\mu(d) \neq 0 当且仅当 dd 中不存在完全平方数因子。显然,具有 ii 个质因数的 dd(ki)\binom{k}{i} 个。因此,dnμ(d)=i=0k(1)k(ki)\sum\limits_{d \mid n} \mu(d) = \sum\limits_{i = 0}^{k} (-1)^k\binom{k}{i}。我们不难观察发现,这个式子就是一个二项式展开,即 (11)k(1 - 1)^k,故其值为 00

莫比乌斯反演

形式 #1

内容

定义 F(n),f(n)F(n), f(n) 均为非负整数集合上的两个函数,则有:

F(n)=dnf(d)f(n)=dnμ(d)F(nd)F(n) = \sum\limits_{d \mid n}f(d) \Leftrightarrow f(n) = \sum\limits_{d \mid n} \mu(d)F(\frac{n}{d})

简而言之,利用莫比乌斯反演,只要我们知道 F(n)F(n) 或是 f(n)f(n) 中一者的定义,就可以推知另一者的具体定义。

证明

下面我们给出莫比乌斯反演的一种简要证明:

dnμ(d)F(nd)=dnμ(d)kndf(k)=knf(k)dnkμ(d)\begin{aligned}
\sum\limits_{d \mid n} \mu(d)F(\frac{n}{d}) = & \sum\limits_{d \mid n} \mu(d) \sum\limits_{k \mid \frac{n}{d}} f(k) \
= & \sum\limits_{k \mid n} f(k) \sum\limits_{d \mid \frac{n}{k}} \mu(d) \
\end{aligned}

由前文提到的性质,当且仅当 nk=1\frac{n}{k} = 1dnkμ(d)=1\sum\limits_{d \mid \frac{n}{k}} \mu(d) = 1;否则该式值为 00。所以:

dnμ(d)F(nd)=f(k)\begin{aligned}
\sum\limits_{d \mid n} \mu(d)F(\frac{n}{d}) = f(k)
\end{aligned}

得证。

形式 #2

内容

定义 F(n),f(n)F(n), f(n) 均为非负整数集合上的两个函数,则有:

F(n)=ndf(d)f(n)=ndμ(dn)F(d)F(n) = \sum\limits_{n \mid d}f(d) \Leftrightarrow f(n) = \sum\limits_{n \mid d} \mu(\frac{d}{n})F(d)

注意这一形式与上一形式最大的不同点,即求和条件由 dnd \mid n 变为 ndn \mid d

证明

t=dnt = \frac{d}{n},有:

ndμ(dn)F(d)=t=1+μ(t)F(nt)=t=1+μ(t)ntkf(k)=nkf(k)tknμ(t)\begin{aligned}
\sum\limits_{n \mid d} \mu(\frac{d}{n})F(d) = & \sum\limits_{t = 1}^{+\infty}\mu(t)F(nt) \
= & \sum\limits_{t = 1}^{+\infty}\mu(t)\sum\limits_{nt \mid k}f(k) \
= & \sum\limits_{n \mid k}f(k)\sum\limits_{t \mid \frac{k}{n}}\mu(t)
\end{aligned}

由前文提到的性质,当且仅当 kn=1\frac{k}{n} = 1tknμ(t)=1\sum\limits_{t \mid \frac{k}{n}}\mu(t) = 1,否则该式值为 00。所以:

ndμ(dn)F(d)=f(n)\sum\limits_{n \mid d} \mu(\frac{d}{n})F(d) = f(n)

应用

F(n)F(n)f(n)f(n) 中一者容易求得,而另一着不易求得时,我们可以借助莫比乌斯反演来求得不易求得的函数。

与欧拉函数联系

这里我们尝试应用一下莫比乌斯反演来推导莫比乌斯函数 μ(n)\mu(n) 与欧拉函数 φ(n)\varphi(n) 间的关系。

首先欧拉函数有一个性质:

dnφ(d)=n\sum\limits_{d \mid n} \varphi(d) = n

那么我们不妨令 F(n)=dnφ(d)=nF(n) = \sum\limits_{d \mid n} \varphi(d) = n,运用莫比乌斯反演可得:

φ(n)=dnμ(d)F(nd)=dnμ(d)nd\begin{aligned}
\varphi(n) = & \sum\limits_{d \mid n} \mu(d)F(\frac{n}{d}) \
= & \sum\limits_{d \mid n} \mu(d) \cdot \frac{n}{d}
\end{aligned}

整理后可得:

dnμ(d)d=φ(n)n\sum\limits_{d \mid n} \frac{\mu(d)}{d} = \frac{\varphi(n)}{n}

注:其实这个结论也可以利用 φ(n)\varphi(n) 的计算公式加上容斥原理得出,而在其过程中,实际上容斥系数就是 μ(d)\mu(d)

与最大公约数联系

给定 n,mn, m,求满足 1in, 1jm, gcd(i,j)=11 \le i \le n, \ 1 \le j \le m, \ \gcd(i, j) = 1 的数对 i,j\langle i, j \rangle 个数(其中 a,b\langle a, b \rangleb,a\langle b, a \rangle 算两个不同的数对)。

换言之,即求:

i=1nj=1m[gcd(i,j)=1]\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m} [\gcd(i, j) = 1]

暴力的做法显然复杂度是 O(n2)\mathcal{O}(n^2) 级别的。

我们可以考虑利用莫比乌斯函数的性质:

i=1nj=1m[gcd(i,j)=1]=i=1nj=1mdgcd(i,j)μ(d)=d=1min(n,m)μ(d)i=1nj=1m[dgcd(i,j)]=d=1min(n,m)μ(d)ndmd\begin{aligned}
\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m} [\gcd(i, j) = 1] = & \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}\sum\limits_{d \mid \gcd(i, j)}\mu(d) \
= & \sum\limits_{d = 1}^{\min(n, m)}\mu(d) \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m} [d \mid \gcd(i, j)] \
= & \sum\limits_{d = 1}^{\min(n, m)} \mu(d)\left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor
\end{aligned}

我们可以用线性筛以 O(N)\mathcal{O}(N) 的复杂度预处理出 μ(n)\mu(n) 的前缀和从而能够 O(1)\mathcal{O}(1) 回答 μ(n)\mu(n) 的区间和。而面对询问时,我们可以用 O(N)\mathcal{O}(\sqrt{N}) 的复杂度进行整除分块并进行求解。


那么如果我们要求的是 gcd(i,j)=k\gcd(i, j) = k 怎么办?我们仅需做如下变换:

i=1nj=1m[gcd(i,j)=k]=i=1nkj=1mk[gcd(i,j)=1]\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m} [\gcd(i, j) = k] = \sum\limits_{i = 1}^{\left\lfloor \frac{n}{k} \right\rfloor}\sum\limits_{j = 1}^{\left\lfloor \frac{m}{k} \right\rfloor} [\gcd(i, j) = 1]

接下来就跟之前的做法一样咯,所以我们能得到:

Ans=d=1min(nk,mk)μ(d)nkdmkdAns = \sum\limits_{d = 1}^{\min(\left\lfloor \frac{n}{k} \right\rfloor, \left\lfloor \frac{m}{k} \right\rfloor)} \mu(d) \left\lfloor \frac{n}{kd} \right\rfloor \left\lfloor \frac{m}{kd} \right\rfloor


当然,我们也可以向莫比乌斯反演的的方向进行考虑。

我们不妨记 f(k)f(k) 代表满足 gcd(i,j)=k\gcd(i, j) = ki,j\langle i, j \rangle 对个数。那么 F(k)=kdf(d)F(k) = \sum\limits_{k \mid d}f(d) 的意义即为满足
kgcd(i,j)k \mid \gcd(i, j)i,j\langle i, j \rangle 对数。而求满足 1in, 1jm1 \le i \le n, \ 1 \le j \le m 范围内 kgcd(i,j)k \mid \gcd(i, j) 这一条件的对数显然等价于 1ink, 1jmk1 \le i \le \left\lfloor \frac{n}{k} \right\rfloor, \ 1 \le j \le \left\lfloor \frac{m}{k} \right\rfloor 范围内 1gcd(i,j)1 \mid \gcd(i, j) 的对数(显然在此范围内的所有数对都满足这一条件)。由此我们可以很容易得到 F(k)F(k) 的具体定义:

F(k)=nkmkF(k) = \left\lfloor \frac{n}{k} \right\rfloor \left\lfloor \frac{m}{k} \right\rfloor

接下来我们就可以利用莫比乌斯反演直接得到 f(k)f(k) 的具体定义了:

f(k)=kdμ(dk)F(d)=kdμ(dk)ndmd\begin{aligned}
f(k) = & \sum\limits_{k \mid d} \mu(\frac{d}{k})F(d) \
= & \sum\limits_{k \mid d} \mu(\frac{d}{k}) \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor \
\end{aligned}

不妨令 t=dkt = \frac{d}{k},我们便得到了跟之前一样的结果:

f(k)=t=1min(nk,mk)μ(t)ntkmtkf(k) = \sum\limits_{t = 1}^{\min(\left\lfloor \frac{n}{k} \right\rfloor, \left\lfloor \frac{m}{k} \right\rfloor)} \mu(t) \left\lfloor \frac{n}{tk} \right\rfloor \left\lfloor \frac{m}{tk} \right\rfloor

至于更多的应用,强烈安利这篇博文: 莫比乌斯反演-让我们从基础开始

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/11/18/mobius-inversion-formula/