莫比乌斯反演学习笔记

Posted on | In |
Words count in article: 1.6k | Reading time ≈ 7

作为一个蒟蒻，最开始看到莫反的时候觉得：这什么毒瘤玩意，溜了溜了。

然而终于大概懂一点了，于是来写一篇博客记录一下。

莫比乌斯反演学习笔记

莫比乌斯函数

在讲莫比乌斯反演前，我们先来看一个新的函数：莫比乌斯函数，记作 $\mu$ 。

$\mu (x)$ 的定义为：

  1. 当 $x = 1$ 时， $\mu (x) = 1$ ；
  2. 当 $x = \prod\limits_{i = 1}^{k}{p_i}$ 且 $p_i$ 为互异质数时， $\mu (x) = (-1)^k$ ；（说人话：将 $x$ 分解质因数后每个质因子的次数都是1，此时函数值由质因子个数决定）
  3. 若 $x$ 有任意一个质因子的次数大于1，则 $\mu (x) = 0$ 。

可以看出莫比乌斯函数有以下几个性质：

  1. 莫比乌斯函数为积性函数，即有 $\mu(ab) = \mu(a) \times \mu(b)$ 。这个比较容易证明，就不证了（懒得打了.jpg）

  2. 对于 $\forall n$ ， $\sum \limits_{d|n} {\mu(d)} = [n =1]$ 。（ $d|n$ 表示 $d$ 整除 $n$ ， $[n = 1]$ 表示 $n = 1$ 这个布尔式的值。）证明如下：

    当 $n = 1$ 时显然成立

    当 $n \ne 1$ 时， $n = p_1^{a_1}p_2^{a_2}p_3^{a_3}…p_k^{a_k}$

    质因子个数为 $r$ 的因子只有 $C_k^r$ 个

    接下来只需要证明以下式子即可

    根据二项式定理

    令 $x = -1\ ,\ y = 1$ 代入即可证。

  3. 对于 $\forall n$ ， $\sum \limits_{d|n} {\frac{\mu(d)} {d}} = \frac{\varphi(n)}{n}$ 。证明如下：

    将欧拉函数的性质写成卷积形式：

    将等式两边同时卷上一个 $\mu$ ，得到：

    得到 $\varphi = N * \mu$ ，展开：

    将两边同时除以 $n$

    于是得证。

然后你就会发现程序实现其实并不是特别困难，只要在线性筛的程序上稍作修改就可以写出了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
il void Get_mu(int n)
{
    mu[1] = 1;
    for (ri i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (ri j = 1; j <= cnt && prime[j] * i <= n; j++)
        {
            vis[prime[j] * i] = 1;
            if (i % prime[j])
                mu[i * prime[j]] = -mu[i];
            else
                break;
        }
    }
}

那么，莫比乌斯函数的讲解就先到这里了，毕竟接下来的才是重点

莫比乌斯反演

在解决完莫比乌斯函数的问题后，我们就开始本文的主题：莫比乌斯反演。

首先讲一个定理： $f(x)$ 和 $g(x)$ 为定义在非负整数集合上的两个函数，且满足 $f(n) = \sum \limits_{d|n}{g(d)}$ ，则存在以下结论：

这个定理就称作莫比乌斯反演定理。（由于已知 $d|n$ 所以没必要加下取整符号）

莫比乌斯反演定理主要有两种证明方式：狄利克雷卷积和定义。

狄利克雷卷积法

已知

将上式写成卷积的形式：

两边同时卷上 $\mu$ ：

又因为有 $\mu * I = \epsilon$ 所以有：

即：

定义法

由 $\mu(\frac{1}{d}) = \mu(d)$ ，代换后可以得出莫比乌斯反演的另一种形式，如果 $f(x)$ 和 $g(x)$ 满足 $g(n) = \sum \limits_{n|d} {f(d)}$ 那么有：

例题：Luogu 2714 四元组统计

题意：给出 $n$ 个正整数，求四元组 $(a_i, a_j, a_k, a_l)$ 使得 $gcd(a_i, a_j, a_k, a_l) = 1$ 的四元组的数量。

思路：其实就是一个组合数学×莫比乌斯反演的模板水题，首先我们不妨设 $f(x)$ 表示 $gcd$ 为 $x$ 的四元组的数量， $g(x)$ 表示 $gcd$ 为 $x$ 的倍数的四元组的个数，所以就是要求 $f(1)$ 。很显然有 $g(n) = \sum \limits_{n|d} {f(d)}$ ，于是根据莫比乌斯反演定理，只要知道 $g$ 就可以求出 $f$ 。而且 $g$ 并不难求，只要知道对于一个数 $i$ ，它的倍数在序列中出现过的次数就可以用组合数求出 $g(i)$ 了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
#define int long long
using namespace std;

const int N = 1e4 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n;
int num[N], mu[N], prime[N], f[N];
bool vis[N];
int C[N][5];

il void Get_C()
{
    C[0][0] = 1;
    for (ri i = 1; i <= N; i++)
    {
        C[i][0] = 1;
        for (ri j = 1; j <= 4; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
}
il void Get_mu()
{
    mu[1] = 1;
    int cnt = 0;
    for (ri i = 2; i <= N; i++)
    {
        if (!vis[i])
        {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (ri j = 1, foo; j <= cnt && (foo = prime[j] * i) <= N; j++)
        {
            vis[foo] = 1;
            if (i % prime[j])
                mu[foo] = -mu[i];
            else
                break;
        }
    }
}

signed main()
{
#ifdef Wepdekr
    freopen("testdata.in", "r", stdin);
#endif
    Get_C();
    Get_mu();
    while (scanf("%lld", &n) == 1)
    {
        memset(num, 0, sizeof(num));
        memset(f, 0, sizeof(f));
        int maxx = -inf, ans = 0;
        for (ri i = 1; i <= n; i++)
        {
            int x = read();
            num[x]++;
            maxx = max(maxx, x);
        }
        for (ri i = maxx; i; i--)
        {
            for (ri j = i; j <= maxx; j += i)
                f[i] += num[j];
            f[i] = C[f[i]][4];
        }
        for (ri i = 1; i <= maxx; i++)
            ans += f[i] * mu[i];
        printf("%lld\n", ans);
    }
    return 0;
}

总结

坑终于填完了QwQ

总之那些看似很复杂实际上真的很复杂的东西终于是讲完了，但是想要熟练的应用还是需要多练习。

下一篇大概肝一个狄利克雷卷积吧（立flag.jpg

0%