莫比乌斯反演

引入

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

开始学习莫比乌斯反演前，需要先学习一些前置知识：

莫比乌斯函数

定义

为莫比乌斯函数，定义为

含 有 平 方 因 子 为 的 本 质 不 同 质 因 子 个 数

详细解释一下：

令，其中为质因子，。上述定义表示：

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

性质

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

即，

证明

设

那么

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

注

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

补充结论

反演结论：

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

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

线性筛

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

线性筛实现

=== "C++"

```cpp
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"

```python
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
```

拓展

证明

将分解质因数：

首先，因为是积性函数，故只要证明当时成立即可。

因为是质数，于是

易知如下过程：

该式子两侧同时卷可得

莫比乌斯变换

设为两个数论函数。

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

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

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

注

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

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

证明

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

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

方法二：运用卷积。

原问题为：已知，证明

易知如下转化：（其中）。

对于第二种形式：

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

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

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

问题形式

「HAOI 2011」Problem b

求值（多组数据）

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

考虑化简该式子

因为时对答案才用贡献，于是我们可以将其替换为（当且仅当时值为否则为），故原式化为

将函数展开得到

变换求和顺序，先枚举可得

易知中的倍数有个，故原式化为

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

时间复杂度

代码实现

#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 50000;
int mu[N + 5], p[N + 5];
bool flg[N + 5];

void init() {
  int tot = 0;
  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];
    }
  }
  for (int i = 1; i <= N; ++i) mu[i] += mu[i - 1];
}

int solve(int n, int m) {
  int res = 0;
  for (int i = 1, j; i <= min(n, m); i = j + 1) {
    j = min(n / (n / i), m / (m / i));
    res += (mu[j] - mu[i - 1]) * (n / i) * (m / i);  // 代推出来的式子
  }
  return res;
}

int main() {
  int T, a, b, c, d, k;
  init();  // 预处理mu数组
  scanf("%d", &T);
  for (int i = 1; i <= T; i++) {
    scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
    // 根据容斥原理，1<=x<=b&&1<=y<=d范围中的答案数减去1<=x<=b&&1<=y<=c-1范围中的答案数和
    //   1<=x<=a-1&&1<=y<=d范围中的答案数再加上1<=x<=a-1&&1<=y<=c-1范围中的答案数
    //   即可得到a<=x<=b&&c<=y<=d范围中的答案数
    // 这一步如果不懂可以画坐标图进行理解
    printf("%d\n", solve(b / k, d / k) - solve(b / k, (c - 1) / k) -
                       solve((a - 1) / k, d / k) +
                       solve((a - 1) / k, (c - 1) / k));
  }
  return 0;
}

「SPOJ 5971」LCMSUM

求值（多组数据）

易得原式即

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

根据，可将原式化为

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

即

可以将相同的合并在一起计算，故只需要统计的个数。当时，，所以的个数有个。

故答案为

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

设，已知为积性函数，于是可以筛出。每次询问计算即可。

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

首先考虑的值，显然它的约数只有，因此

又有，则原式可化为

于是有

那么，对于线性筛中的，令，可得

即

同理有

因此

时间复杂度：

代码实现

#include <cstdio>
const int N = 1000000;
int tot, p[N + 5];
long long g[N + 5];
bool flg[N + 5];  // 标记数组

void solve() {
  g[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!flg[i]) {
      p[++tot] = i;
      g[i] = (long long)1 * i * (i - 1) + 1;
    }
    for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        g[i * p[j]] =
            g[i] + (g[i] - g[i / p[j]]) * p[j] * p[j];  // 代入推出来的式子
        break;
      }
      g[i * p[j]] = g[i] * g[p[j]];
    }
  }
}

int main() {
  int T, n;
  solve();  // 预处理g数组
  scanf("%d", &T);
  for (int i = 1; i <= T; ++i) {
    scanf("%d", &n);
    printf("%lld\n", (g[n] + 1) * n / 2);
  }
  return 0;
}

「BZOJ 2154」Crash 的数字表格

求值（对取模）

易知原式等价于

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

非常经典的式子的化法

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

接下来对进行化简。首先枚举约数，并将表示为

设，，显然式子可以变为

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

可以求解

至此

我们可以数论分块求解函数。

在求出后，回到定义的地方，可得原式为

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

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

时间复杂度：（瓶颈为线性筛）

代码实现

#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 1e7;
const int mod = 20101009;
int n, m, mu[N + 5], p[N / 10 + 5], sum[N + 5];
bool flg[N + 5];

int Sum(int x, int y) {
  return ((long long)1 * x * (x + 1) / 2 % mod) *
         ((long long)1 * y * (y + 1) / 2 % mod) % mod;
}

int func(int x, int y) {
  int res = 0;
  int j;
  for (int i = 1; i <= min(x, y); i = j + 1) {
    j = min(x / (x / i), y / (y / i));
    res = (res + (long long)1 * (sum[j] - sum[i - 1] + mod) *
                     Sum(x / i, y / i) % mod) %
          mod;  //+mod防负数
  }
  return res;
}

int solve(int x, int y) {
  int res = 0;
  int j;
  for (int i = 1; i <= min(x, y); i = j + 1) {  // 整除分块处理
    j = min(x / (x / i), y / (y / i));
    res = (res + (long long)1 * (j - i + 1) * (i + j) / 2 % mod *
                     func(x / i, y / i) % mod) %
          mod;  // ！每步取模防爆
  }
  return res;
}

void init() {  // 线性筛
  mu[1] = 1;
  int tot = 0, k = min(n, m);
  for (int i = 2; i <= k; ++i) {
    if (!flg[i]) {
      p[++tot] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= tot && i * p[j] <= k; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= k; ++i)
    sum[i] = (sum[i - 1] + (long long)1 * i * i % mod * (mu[i] + mod)) % mod;
}

int main() {
  scanf("%d%d", &n, &m);
  init();
  printf("%d\n", solve(n, m));
}

「SDOI2015」约数个数和

多组数据，求

其中，表示的约数个数

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

再化一下这个式子

将上述式子代回原式

那么预处理的前缀和，分块处理询问，总复杂度 .

代码实现

#include <algorithm>
#include <cstdio>
using namespace std;
const long long N = 5e4 + 5;
long long n, m, T, pr[N], mu[N], d[N], t[N],
    cnt;  // t 表示 i 的最小质因子出现的次数
bool bp[N];

void prime_work(long long k) {
  bp[0] = bp[1] = 1, mu[1] = 1, d[1] = 1;
  for (long long i = 2; i <= k; i++) {  // 线性筛
    if (!bp[i]) pr[++cnt] = i, mu[i] = -1, d[i] = 2, t[i] = 1;
    for (long long j = 1; j <= cnt && i * pr[j] <= k; j++) {
      bp[i * pr[j]] = 1;
      if (i % pr[j] == 0) {
        mu[i * pr[j]] = 0;
        d[i * pr[j]] = d[i] / (t[i] + 1) * (t[i] + 2);
        t[i * pr[j]] = t[i] + 1;
        break;
      } else {
        mu[i * pr[j]] = -mu[i];
        d[i * pr[j]] = d[i] << 1;
        t[i * pr[j]] = 1;
      }
    }
  }
  for (long long i = 2; i <= k; i++)
    mu[i] += mu[i - 1], d[i] += d[i - 1];  // 求前缀和
}

long long solve() {
  long long res = 0, mxi = min(n, m);
  for (long long i = 1, j; i <= mxi; i = j + 1) {  // 整除分块
    j = min(n / (n / i), m / (m / i));
    res += d[n / i] * d[m / i] * (mu[j] - mu[i - 1]);
  }
  return res;
}

int main() {
  scanf("%lld", &T);
  prime_work(50000);  // 预处理
  while (T--) {
    scanf("%lld%lld", &n, &m);
    printf("%lld\n", solve());
  }
  return 0;
}

另一种推导方式

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

容易知道

设，继续接着前面的往下推

利用反演，上式等于

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