资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

莫比乌斯反演详解：从基础概念到实际应用

创作时间:

作者:

@小白创作中心

莫比乌斯反演详解：从基础概念到实际应用

引用

CSDN

https://m.blog.csdn.net/w_w_wwwww/article/details/145344538

莫比乌斯反演是数论中的一个重要工具，主要用于解决一些函数的求值问题。当直接求解某个函数的值较为困难时，如果能够容易地求出其倍数和或约数和，那么可以通过莫比乌斯反演简化运算，求得原函数的值。本文将从莫比乌斯函数的定义出发，逐步介绍其性质、线性筛实现方法以及莫比乌斯变换等内容，并通过多个具体例题展示其在实际问题中的应用。

引入

莫比乌斯反演是数论中的重要内容。对于一些函数

，如果很难直接求出它的值，而容易求出其倍数和或约数和
，那么可以通过莫比乌斯反演简化运算，求得
的值。
开始学习莫比乌斯反演前，需要先学习一些前置知识：数论分块、狄利克雷卷积。

莫比乌斯函数

定义

为莫比乌斯函数，定义为
含有平方因子为的本质不同质因子个数
详细解释一下：
令
，其中
为质因子，
。上述定义表示：

时，
；
对于
时：
当存在
，使得
时，
，也就是说只要某个质因子出现的次数超过一次，
就等于
；
当任意
，都有
时，
，也就是说每个质因子都仅仅只出现过一次时，即
，
中个元素唯一时，
等于
的
次幂，此处指的便是仅仅只出现过一次的质因子的总个数。

性质

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

证明

设
那么
根据二项式定理，易知该式子的值在即时值为否则为，这也同时证明了以及

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

补充结论

反演结论：

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

利用函数：根据上一结论，，将展开即可。

线性筛

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

线性筛实现

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];
    }
  }
}

拓展

证明

将分解质因数：
首先，因为是积性函数，故只要证明当时成立即可。
因为是质数，于是
易知如下过程：
该式子两侧同时卷可得

莫比乌斯变换

设为两个数论函数。
形式一：如果有，那么有。
这种形式下，数论函数称为数论函数的莫比乌斯变换，数论函数称为数论函数的莫比乌斯逆变换（反演）。
容易看出，数论函数的莫比乌斯变换，就是将数论函数与常数函数进行狄利克雷卷积。

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

形式二：如果有，那么有。

证明

方法一：对原式做数论变换。
用来替换，再变换求和顺序。最后一步变换的依据：，因此在
时第二个和式的值才为。此时，故原式等价于

方法二：运用卷积。
原问题为：已知，证明
易知如下转化：（其中）。
对于第二种形式：
类似上面的方法一，我们考虑逆推这个式子。
我们把表示为的形式，然后把
的原定义代入式子。
发现枚举
再枚举
的倍数可以转换为直接枚举的倍数再求出
，发现后面那一块其实就是
, 整个式子只有在
的时候才能取到值。

问题形式

「HAOI 2011」Problem b

求值（多组数据）
根据容斥原理，原式可以分成
块来处理，每一块的式子都为
考虑化简该式子
因为
时对答案才用贡献，于是我们可以将其替换为
（
当且仅当
时值为
否则为
），故原式化为
将
函数展开得到
变换求和顺序，先枚举
可得
易知
中
的倍数有
个，故原式化为
很显然，式子可以数论分块求解。

时间复杂度

代码实现

「SPOJ 5971」LCMSUM

求值（多组数据）
易得原式即
将原式复制一份并且颠倒顺序，然后将 n 一项单独提出，可得
根据
，可将原式化为
两个求和式中分母相同的项可以合并。
即
可以将相同的
合并在一起计算，故只需要统计
的个数。当
时，
，所以
的个数有
个。
故答案为
变换求和顺序，设
，合并公因式，式子化为
设
，已知为积性函数，于是可以
筛出。每次询问
计算即可。
下面给出这个函数筛法的推导过程：
首先考虑
的值，显然它的约数只有
，因此
又有
，则原式可化为
于是有
那么，对于线性筛中的，令
，可得
即
同理有
因此
时间复杂度：

代码实现

「BZOJ 2154」Crash 的数字表格

求值（对
取模）
易知原式等价于
枚举最大公因数
，显然两个数除以
得到的数互质
非常经典的式子的化法
后半段式子中，出现了互质数对之积的和，为了让式子更简洁就把它拿出来单独计算。于是我们记
接下来对进行化简。首先枚举约数，并将
表示为
设
，
，显然式子可以变为
观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记
可以
求解
至此
我们可以
数论分块求解
函数。
在求出
后，回到定义
的地方，可得原式为
可见这又是一个可以数论分块求解的式子！
本题除了推式子比较复杂、代码细节较多之外，是一道很好的莫比乌斯反演练习题！（上述过程中，默认
）
时间复杂度：
（瓶颈为线性筛）