莫比乌斯反演(二):莫比乌斯函数

莫比乌斯函数

前言

莫比乌斯函数,数论函数,由德国数学家和天文学家莫比乌斯(August Ferdinand Möbius ,1790–1868)提出。梅滕斯(Mertens)首先使用 $\mu(d)$作为莫比乌斯函数的记号。而据说,高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数。莫比乌斯函数在数论中有着广泛应用。

莫比乌斯函数  $\mu(d)$

莫比乌斯函数表达式:

由上式可知 $\mu(6) = 1$ 因为 $6=2*3$,而 $\mu(12) = 0$ 因为 $12 = 2*2*3 = 2^2*3$。
特别需要注意的是 $\mu(1) = 1$。

莫比乌斯函数的性质

  1. 约束求和:或者PS:$[n=1]$ 表示当 $n=1$ 时为 $1$ ,否则为 $0$ 。
    证明:当 $n=1$ 时,显然成立。当 $n>1$ 时,将 $n$ 改写为 $p_1\cdot p_2 \cdots p_k$。
    设集合 $P = \{p_1,p_2,\cdots,p_k\}$ 。
    若使 $d|n$ ,当且仅当 $d$ 为集合 $P$ 中的某些元素的乘积。因此可得:
  2. 这个性质只列出,暂时不作证明

以上两条是莫比乌斯函数最常用的性质。

莫比乌斯函数筛法

1.最简单的筛法:

1
2
3
4
5
6
7
8
void get_mu() {
mu[1] = 1;
for (int i = 1; i < maxn; i++) {
for (int j = i + i; j < maxn; j += i) {
mu[j] -= mu[i];
}
}
}

2.线性筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void get_mu() {
mu[1] = 1;
for (int i = 2; i < maxn; i++) {
if (vis[i] == false) {
prime[cnt++] = i;
mu[i] = -1;
}
for (int j = 0; j < cnt && i * prime[j] < maxn; j++) {
vis[i * prime[j]] = true;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
} else {
mu[i * prime[j]] = -mu[i];
}
}
}