莫比乌斯反演

莫比乌斯反演¶

莫比乌斯反演是数论中的重要内容。对于一些函数 f(n)，如果很难直接求出它的值，而容易求出其倍数和或约数和 g(n)，那么可以通过莫比乌斯反演简化运算，求得 f(n) 的值。

开始学习莫比乌斯反演前，需要先学习一些前置知识：数论分块、狄利克雷卷积。

莫比乌斯函数¶

定义¶

μ 为莫比乌斯函数，定义为

详细解释一下：

令 n=∏i=1kpici，其中 pi 为质因子，ci≥1。上述定义表示：

1. n=1 时，μ(n)=1；
2. 对于 n≠1 时：
   1. 当存在 i∈[1,k]，使得 ci>1 时，μ(n)=0，也就是说只要某个质因子出现的次数超过一次，μ(n) 就等于 0；
   2. 当任意 i∈[1,k]，都有 ci=1 时，μ(n)=(−1)k，也就是说每个质因子都仅仅只出现过一次时，即 n=∏i=1kpi，{pi}i=1k 中个元素唯一时，μ(n) 等于 −1 的 k 次幂，此处 k 指的便是仅仅只出现过一次的质因子的总个数。

性质¶

莫比乌斯函数不仅是积性函数，还有如下性质：

即 ∑d∣nμ(d)=ε(n)，μ∗1=ε

证明¶

设 n=∏i=1kpici,n′=∏i=1kpi

那么 ∑d∣nμ(d)=∑d∣n′μ(d)=∑i=0kCki⋅(−1)i=(1+(−1))k

根据二项式定理，易知该式子的值在 k=0 即 n=1 时值为 1 否则为 0，这也同时证明了 ∑d∣nμ(d)=[n=1]=ε(n) 以及 μ∗1=ε

注

这个性质意味着，莫比乌斯函数在狄利克雷生成函数中，等价于黎曼函数 ζ 的倒数。所以在狄利克雷卷积中，莫比乌斯函数是常数函数 1 的逆元。

补充结论¶

反演结论：[gcd(i,j)=1]=∑d∣gcd(i,j)μ(d)

直接推导：如果看懂了上一个结论，这个结论稍加思考便可以推出：如果 gcd(i,j)=1 的话，那么代表着我们按上个结论中枚举的那个 n 是 1，也就是式子的值是 1，反之，有一个与 [gcd(i,j)=1] 相同的值：0

利用 ε 函数：根据上一结论，[gcd(i,j)=1]=ε(gcd(i,j))，将 ε 展开即可。

线性筛¶

由于 μ 函数为积性函数，因此可以线性筛莫比乌斯函数（线性筛基本可以求所有的积性函数，尽管方法不尽相同）。

线性筛实现

// C++ Version
void getMu() {
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!flg[i]) p[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
}

# Python Version
def getMu():
mu[1] = 1
for i in range(2, n + 1):
    if flg[i] != 0:
        p[tot] = i; tot = tot + 1; mu[i] = -1
    j = 1
    while j <= tot and i * p[j] <= n:
        flg[i * p[j]] = 1
        if i % p[j] == 0:
            mu[i * p[j]] = 0
            break
        mu[i * p[j]] = mu[i * p[j]] - mu[i]
        j = j + 1

拓展¶

将 n 分解质因数：n=∏i=1kpici

首先，因为 φ 是积性函数，故只要证明当 n′=pc 时 φ∗1=∑d∣n′φ(n′d)=id 成立即可。

因为 p 是质数，于是 d=p0,p1,p2,⋯,pc

易知如下过程：

该式子两侧同时卷 μ 可得 φ(n)=∑d∣nd⋅μ(nd)

莫比乌斯变换¶

设 f(n),g(n) 为两个数论函数。

形式一：如果有 f(n)=∑d∣ng(d)，那么有 g(n)=∑d∣nμ(d)f(nd)。

这种形式下，数论函数 f(n) 称为数论函数 g(n) 的莫比乌斯变换，数论函数 g(n) 称为数论函数 f(n) 的莫比乌斯逆变换（反演）。

容易看出，数论函数 g(n) 的莫比乌斯变换，就是将数论函数 g(n) 与常数函数 1 进行狄利克雷卷积。

注

根据狄利克雷卷积与狄利克雷生成函数的对应关系，数论函数 g(n) 的莫比乌斯变换对应的狄利克雷生成函数，就是数论函数 g(n) 的狄利克雷生成函数与黎曼函数 ζ 的乘积。

形式二：如果有 f(n)=∑n|dg(d)，那么有 g(n)=∑n|dμ(dn)f(d)。

证明¶

方法一：对原式做数论变换。

用 ∑d∣ng(d) 来替换 f(nd)，再变换求和顺序。最后一步变换的依据：∑d∣nμ(d)=[n=1]，因此在 nk=1 时第二个和式的值才为 1。此时 n=k，故原式等价于 ∑k∣n[n=k]⋅g(k)=g(n)

方法二：运用卷积。

原问题为：已知 f=g∗1，证明 g=f∗μ

易知如下转化：f∗μ=g∗1∗μ⟹f∗μ=g（其中 1∗μ=ε）。

对于第二种形式：

类似上面的方法一，我们考虑逆推这个式子。

我们把 d 表示为 kn 的形式，然后把 f 的原定义代入式子。

发现枚举 k 再枚举 kn 的倍数可以转换为直接枚举 n 的倍数再求出 k，发现后面那一块其实就是 ϵ, 整个式子只有在 d=n 的时候才能取到值。

问题形式¶

「HAOI 2011」Problem b¶

求值（多组数据）

根据容斥原理，原式可以分成 4 块来处理，每一块的式子都为

考虑化简该式子

因为 gcd(i,j)=1 时对答案才用贡献，于是我们可以将其替换为 ε(gcd(i,j))（ε(n) 当且仅当 n=1 时值为 1 否则为 0），故原式化为

将 ε 函数展开得到

变换求和顺序，先枚举 d∣gcd(i,j) 可得

易知 1∼⌊nk⌋ 中 d 的倍数有 ⌊nkd⌋ 个，故原式化为

很显然，式子可以数论分块求解。

时间复杂度 Θ(N+Tn)

代码实现

「SPOJ 5971」LCMSUM¶

求值（多组数据）

易得原式即

将原式复制一份并且颠倒顺序，然后将 n 一项单独提出，可得

根据 gcd(i,n)=gcd(n−i,n)，可将原式化为

两个求和式中分母相同的项可以合并。

可以将相同的 gcd(i,n) 合并在一起计算，故只需要统计 gcd(i,n)=d 的个数。当 gcd(i,n)=d 时，gcd(id,nd)=1，所以 gcd(i,n)=d 的个数有 φ(nd) 个。

变换求和顺序，设 d′=nd，合并公因式，式子化为

设 g⁡(n)=∑d∣nd⋅φ(d)，已知 g 为积性函数，于是可以 Θ(n) 筛出。每次询问 Θ(1) 计算即可。

下面给出这个函数筛法的推导过程：

首先考虑 g⁡(pjk) 的值，显然它的约数只有 pj0,pj1,⋯,pjk，因此

又有 φ(pjw)=pjw−1⋅(pj−1)，则原式可化为

那么，对于线性筛中的 g⁡(i⋅pj)(pj|i)，令 i=a⋅pjw(gcd⁡(a,pj)=1)，可得

时间复杂度：Θ(n+T)

代码实现

「BZOJ 2154」Crash 的数字表格¶

求值（对 20101009 取模）

易知原式等价于

枚举最大公因数 d，显然两个数除以 d 得到的数互质

非常经典的 gcd 式子的化法

后半段式子中，出现了互质数对之积的和，为了让式子更简洁就把它拿出来单独计算。于是我们记

接下来对 sum⁡(n,m) 进行化简。首先枚举约数，并将 [gcd(i,j)=1] 表示为 ε(gcd(i,j))

设 i=i′⋅d，j=j′⋅d，显然式子可以变为

观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记

可以 Θ(1) 求解

我们可以 ⌊n⌊nd⌋⌋ 数论分块求解 sum⁡(n,m) 函数。

在求出 sum⁡(n,m) 后，回到定义 sum 的地方，可得原式为

可见这又是一个可以数论分块求解的式子！

本题除了推式子比较复杂、代码细节较多之外，是一道很好的莫比乌斯反演练习题！（上述过程中，默认 n⩽m）

时间复杂度：Θ(n+m)（瓶颈为线性筛）

代码实现

「SDOI2015」约数个数和¶

多组数据，求

其中 d(n) 表示 n 的约数个数

要推这道题首先要了解 d 函数的一个特殊性质

再化一下这个式子

将上述式子代回原式

那么 O(n) 预处理 μ,d 的前缀和，O(n) 分块处理询问，总复杂度 O(n+Tn).

代码实现

另一种推导方式

转化一下，可以将式子写成

设 F(n)=∑i=1ni，继续接着前面的往下推

利用 id∗μ=φ 反演，上式等于

∑T=1nF2(⌊nT⌋)T2φ(T)

得到了一个与第一种推导本质相同的式子。

莫比乌斯反演扩展¶

结尾补充一个莫比乌斯反演的非卷积形式。

对于数论函数 f,g 和完全积性函数 t 且 t(1)=1：

我们证明一下

参考文献¶

algocode 算法博客