莫比乌斯反演

发表于 更新于 分类于 ， 阅读次数： 本文字数： 15k 阅读时长 ≈ 28 分钟

前言

没有人比你更懂莫反。

前置芝士

积性函数

定义

若函数 $f(x)$ 满足 $f(x)=1$ 且对于任意两个互质的正整数 $x,y$ 满足 $f(x\times y)=f(x)\times f(y)$，则 $f(x)$ 为积性函数。

完全积性函数

对于任意正整数 $x,y$ 都有 $f(x\times y)=f(x)\times f(y)$，则 $f(x)$ 为完全积性函数。

性质

若 $f(x), g(x)$ 都为积性函数，那么 $f(x)*g(x)$ 为积性函数。

常用积性函数

  1. $I(x)=1$ （完全积性）
  2. $id_k(x)=x^k,id_1(n)$ 简记为 $id(n)=n$ （完全积性）
  3. $\varepsilon(x)=[x==1]$
  4. $\varphi(x)=n\prod_{p|n}(1-\frac{1}{p})$ （欧拉函数，即 $1\sim n$ 中与 $n$ 互质的数的个数）
  5. $d(x)=\prod_{1}^{k}(p_i+1)$，$p_i$ 为质因子 $q_i$ 的幂数。
  6. $\sigma_1(x)=\sum_{d|x}d$
  7. \begin{align}
    \mu(n)= \begin{cases}
    0 & 存在 p^q(q\geq 2),p^a|n\\
    (-1)^k & n=p_1\times p_2\times…\times p_k\\
    1 & n=1
    \end{cases}
    \end{align}

通用求法

因为是积性函数，所以用线性筛即可处理。

狄利克雷卷积

形式

$(f*g)(n)=\sum_{d|n} f(d)g(\frac{n}{d})$

推论

  1. 两个积性函数的卷积也是积性函数
  2. 满足结合律，交换律， 函数加法分配律，而单位元则是 $\varepsilon(x)$
  3. $d(x)=(I*I)(x)$。
  4. $(Id)(x)=(\varphi*I)(x)$
  5. $\varepsilon(x)=(\mu*I)(x)$
  6. $\varphi(x)=(\mu*Id)(x)$

莫比乌斯反演

形式 1

$f(n)=\sum_{d|n} g(d)I(\frac{n}{d})\leftrightarrow g(n)=\sum_{d|n}f(d)\mu(\frac{n}{d})$
用狄利克雷卷积卷一下即可。

形式 2

$f(n)=\sum_{n|d}g(d)I(\frac{d}{n})\leftrightarrow g(n)=\sum_{n|d}f(d)\mu(\frac{d}{n})$
推演如下(左推右)：
\begin{align}
& \sum_{n|d}\mu(\frac{d}{n})f(d)\\
= & \sum_{k=1}^{+\infty}\mu(k)f(nk)\\
= & \sum_{k=1}^{+\infty}\mu(k)\sum_{(kn)|d}g(d)\\
= & \sum_{n|d}g(d)\sum_{k|\frac{d}{n}}\mu(k)\\
= & \sum_{n|d}g(d)\times (\mu*I)(\frac{d}{n})\\
= & \sum_{n|d}g(d)\varepsilon(\frac{d}{n})\\
= & g(n)
\end{align}
以上两者为基本式子。

数论分块

一种非常简单的小清新玩意，还是结合题来讲要好讲一些。（因为是数论，下文自动省略向下取整）
例：UVA11526 H(n)，给定 $n$，求 $\sum_{d=1}^{n}\frac{n}{d}$。
这种题，乍一看只能用 $O(n)$ 的算法来解决。然后就有了神奇的数论分块：
我们可以将原来的数列分成一些块，使得块内的值 $\frac{n}{i}$ 相等。不难发现：如果当前块的左端点为 $l$，则右端点为 $n/(n/l)$（括号内向下取整）。同时，块数不大于 $2\sqrt{n}$，所以算法复杂度为 $O(\sqrt{n})$。
当然，常和一些公式配套使用：
\begin{align}
& \sum_{i=1}^{n}i^2=\frac{n(n+1)(n+2)}{6}\\
& \sum_{i=1}^{n}i^3=(\sum_{i=1}^{n}i)^2
\end{align}
故这个题就可以非常简单粗暴地解决掉。核心代码：

例题讲解

P1390 公约数的和

link，这是莫反的基础式子，学会这个你就入土门了。
重要思想：枚举公约数。
\begin{align}
& \sum_{i=1}^{n}\sum_{j=i+1}^{n}\gcd(i,j)\\
= & \sum_{d}\sum_{i=1}^{n}\sum_{j=i+1}^nd\times [\gcd(i,j)==d]\\
= & \sum_d\sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d}d\times [\gcd(i,j)=1]\\
= & \sum_dd\sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d}\varepsilon(\gcd(i,j))\\
= & \sum_dd\sum_{i=1}^{n/d}\varphi(i)
& \end{align}
（虽然但是，这好像是欧拉反演）
接下来只要预处理 $\varPhi(x)$ 的前缀和，然后数论分块即可在 $O(n)$ 的时间内解决。

然而还有真正的莫比乌斯反演解法。
从上式倒数第二步开始：
\begin{align}
= & \sum_dd\sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d}\varepsilon(\gcd(i,j))\\
= & \frac{1}{2}(\sum_dd\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\sum_{k|i,k|j}\mu(k)-\frac{n\times(n+1)}{2})
\end{align}
这里换一下概念，以 $T$ 来代替 $d$，再用新的 $d$ 代替 $k$。
\begin{align}
& \sum_TT\sum_{i=1}^{n/T}\sum_{j=1}^{n/T}\sum_{d|i,d|j}\mu(d)\\
= & \sum_TT\sum_{d=1}\mu(d)\lfloor\frac{n}{Td}\rfloor\lfloor\frac{n}{Td}\rfloor
\end{align}
但是这样还是很麻烦，于是我们考虑将 $Td$ 打包，枚举约数。（即枚举 $Td$，再枚举其约数 $d$）
\begin{align}
& \sum_T\lfloor\frac{n}{T}\rfloor^2\sum_{d|T}d\times\mu(\frac{T}{d})\\
= & \sum_T\lfloor\frac{n}{T}\rfloor^2\varphi(T)
\end{align}
代入原式：$\frac{1}{2}(\sum_T\lfloor\frac{n}{T}\rfloor^2\varphi(T)-\frac{n\times(n+1)}{2})$，然后愉快的数论分块即可了。

P2231 [HNOI2002] 跳蚤

link，比较中规中矩。
根据裴蜀定理，形式化为：
\begin{align}
\sum_{1\leq k_i\leq m, i\in [1,n]} \varepsilon(\gcd(\gcd(k_i), m))
\end{align}
然后大力化式子：

\begin{align}
& \sum_{1\leq k_i\leq m, i\in [1,n]}\varepsilon(\gcd(\gcd(k_i), m))\\
= & \sum_{1\leq k_i\leq m, i\in [i,n]}\sum_{d|k_i,d|m}\mu(d)\\
= & \sum_{d|m}\sum_{1\leq k_i\leq m,1\leq i\leq n}\varepsilon(d|k_i)\\
= & \sum_{d|m}(\frac{m}{d})^n
\end{align}

然后就没有然后了，直接暴力枚举约数然后统计就行了，复杂度 $O(\sqrt{m}\log m)$。

P1829 [国家集训队] Crash的数字表格 / JZPTAB

link，数论分块套数论分块
直接考虑化式子（假定 $n\leq m$）：
\begin{align}
& \sum_{i=1}^n\sum_{j=1}^mlcm(i,j)\\
= & \sum_{i=1}^n\sum_{j=1}^m\frac{i\times j}{\gcd(i,j)}\\
= & \sum_{d=1}^n\sum_{i|d}^n\sum_{j|d}^m\frac{i\times j}{\gcd(i,j)}[\gcd(i,j)=d]\\
= & \sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}i\times j\times[\gcd(i,j)=1]
\end{align}
直接搞得话没那么容易，我们把其中一部分提出来：
令 $f(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}i\times j\times[\gcd(i,j)=1]$。
化式子：

\begin{align}
& \sum_{i=1}^n\sum_{j=1}^mi\times j\times[\gcd(i,j)=1]\\
= & \sum_{d=1}^n\sum_{i|d}^n\sum_{j|d}^m\mu(d)\times i\times j\\
= & \sum_{d=1}^n\mu(d)\times d^2\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j\\
= & \sum_{d=1}^n\mu(d)\times d^2\times\frac{\lfloor\frac{n}{d}\rfloor\times(\lfloor\frac{n}{d}\rfloor+1)}{2}\times\frac{\lfloor\frac{m}{d}\rfloor\times(\lfloor\frac{m}{d}\rfloor+1)}{2}
\end{align}
至此，这个式子已经可以用数论分块解决。
那么原式化为：$\sum_{d=1}^nd\times f(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$，再套一层数论分块即可。复杂度 $O(n+m)$。

P3312 [SDOI2014] 数表

link，很有意思。
重点不在化式子，故一笔带过。
\begin{align}
& \sum_{i=1}^n\sum_{j=1}^{m}\sigma_1(\gcd(i,j))\\
= & \sum_{T=1}^n\lfloor\frac{n}{T}\frac{m}{T}\sum_{d|T}\sigma_1(d)\mu(\frac{T}{d})
\end{align}
那么，问题就在于不大于 $a$ 的限制上。只有当 $\sigma_1(d)\leq a$ 时，才会对答案产生贡献。
那么就考虑把询问离线，按 $a$ 的值从小到大排序，然后将新加入的值放进树状数组里面维护（新加入值，直接枚举倍数，然后树状数组枚举前缀和），没了。

P3704 [SDOI2017] 数字表格

link，预处理大法好。
观察式子：
\begin{align}
& \prod_{i=1}^n\prod_{j=1}^mf_{\gcd(i,j)}\\
= & \prod_{d=1}^nf_d^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)==d]}
\end{align}
直接一步跳过：
\begin{align}
& \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)==1]\\
= & \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor
\end{align}
那么代入原式子：
\begin{align}
\prod_{T=1}^n(\prod)_{d|T}(f_d^{\mu(\frac{T}{d})})^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}
\end{align}
然后就没有然后了，暴力预处理里面那一坨对倍数算贡献 $O(n\log n)$ 的复杂度，然后 $O(\sqrt{n})$ 算就完了。

尾声

如果你终于入门了，请尝试：[MtOI2019]幽灵乐团/莫比乌斯反演基础练习题。