莫比乌斯反演

在看这篇文章的时候,最好拿出草稿纸在该推的地方动手推一下

文章里面函数定义域都是 $Z_+$。

前置芝士

莫比乌斯反演的大概意义

知道 $F$ 与 $f$ 的关系,反推出 $f$ 与 $F$ 的关系

请注意,这里的 $f$ 和 $F$ 均是函数

整除分块

实际上和莫比乌斯反演关系不大,主要是应用到题目里面经常要用。

一种 $O(\sqrt{n})$ 求得

$$
\sum_{i = 1}^{n} \lfloor \frac{n}{i} \rfloor
$$

的方法。

朴素扫描显然是 $O(n)$ 的。但是仔细观察可以发现,答案实际上被分为了几个内部元素相同的块。

例如当 $n = 10$ 时,答案分别为:

$$
\lfloor \frac{10}{1} \rfloor, \lfloor \frac{10}{2} \rfloor, \cdots,\lfloor \frac{10}{10} \rfloor
$$

$$
[10], [5], [3], [2, 2], [1, 1, 1, 1, 1]
$$

用 $[\ ]$ 括起来的就是所描述的块。

既然块内元素相同,那么再扫描过去显然是没有必要的;这时,就可以使用一个玄学的公式,得到当前块的区间的右端点:

$$
\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor
$$

证明?不会

写成代码就是:

1
2
3
4
5
6
int ans = 0;
for (register int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l);
ans += (r - l + 1) * (n / l);
}

复杂度大概是 $O(\sqrt{n})$ 一样不会证

各类定义

$d|n$ :$d$ 整除 $n$,即 $d$ 为 $n$ 的因子

$(a, b)$:$a, b$ 的最大公因数,即 $\text{gcd}(a, b)$

$C^k_n$:组合数,即从 $n$ 个物品中选出 $k$ 个物品的方案数

$[P]$:命题 $P$ 成立,值为 $1$;否则为 $0$

$w(n)$:$n$ 的不同质因子的个数,特别地,$w(1) = 0$

欧拉函数 $\varphi(n)$:小于等于 $n$ 的正整数中,与 $n$ 互质的数的个数,$\varphi(1) = 1$

积性函数:当 $\text{gcd}(a,b) = 1$ 时,函数 $f$ 满足 $f(ab) = f(a) \times f(b)$,则称 $f$ 为积性函数。

完全积性函数:去掉 $\text{gcd}(a,b)=1$ 的限制,即对于任意的 $a, b$,函数 $f$ 都有 $f(ab) = f(a) \times f(b)$,则称 $f$ 为完全积性函数。

狄利克雷卷积

如开头所说,我们首先需要知道 $F$ 和 $f$ 的关系。

狄利克雷卷积正是数学家发明的用于表达函数间关系的运算。

对于算术函数 $f, g$,定义其狄利克雷卷积为:

$$
(f \ast g)(n) = \sum_{d | n} f(d)g(\frac n d)
$$

其中的 $\ast$ 即为狄利克雷卷积,你可以将 $(f \ast g)$ 视作一个新函数 $h$,后面的 $(n)$ 是 $h$ 的自变量。

通俗点讲,它就是一种运算符,和 $+, -, \times, \div$ 没有任何区别;

只不过加减乘除对进行运算,而 $\ast$ 是对函数进行运算。

类似于我们称 $a \times b$ 为“ $a$ 乘 $b$ ”,我一般称 $a \ast b$ 为“ $a$ 卷 $b$ ”。

下面给出一些性质(摘自维基百科):

  1. 交换律:$f \ast g = g \ast f$。
  2. 结合律:$f \ast (g \ast h) = (f \ast g) \ast h$
  3. 存在单位函数 $\epsilon(n) = [n = 1]$,使得任意算术函数 $f$ 都满足 $f \ast \epsilon = f$。
  4. 若 $f, g$ 为积性函数,那么 $f \ast g$ 也是积性函数。
  5. 对于任意算术函数 $f$,若 $f(1) \not= 0$,都有唯一的逆函数 $f^{-1}$,使得 $f^{-1} \ast f = \epsilon$。

1 的证明:显然,

$$
(f \ast g)(n) = \sum_{d | n} f(d)g(\frac n d) = \sum_{d | n} f(\frac n d) g(d) = (g \ast f)(n)
$$

4 的证明:$(a, b) = 1$ 时,

$$
\begin{aligned}
(f \ast g)(a) \times (f \ast g)(b) &= (\sum_{u|a} f(u)g(\frac{a}{u})) \times (\sum_{v|b} f(v)g(\frac{b}{v})) \\
&= \sum_{u|a} \sum_{v|b} f(u)g(\frac{a}{u})f(v)g(\frac{b}{v} ) \\
&= \sum_{u|a} \sum_{v|b} f(uv)g(\frac{ab}{uv}) \\
&= \sum_{d|ab} f(d)g(\frac{ab}{d}) \\
&= (f \ast g)(ab)
\end{aligned}
$$

$uv$ 可以变成 $d$,是因为 $(a, b) = 1$。(仔细想想为什么)

$\epsilon(n)$ 用人话来讲就是判断一个数是否为 $1$,是函数值就是 $1$,否则就是 $0$。

结合律和 $f \ast \epsilon = f$ 的证明,请手推一下。

逆函数的话暂且不用管,不过你应该也可以想到反演会与逆函数有关了- -

莫比乌斯函数

定义:

$$
\mu(n) = \begin{cases}
1, & n = 1 \\
(-1)^{w(n)}, & n\text{ 的质因子的最大幂次不超过 }1 \\
0, & \text{其余情况}
\end{cases}
$$

易证其为积性函数。

引理:

$$
\sum_{d|n} \mu(d) = \begin{cases}
1, & n = 1 \\
0, & n > 1
\end{cases}
$$

等号右边其实就是 $\epsilon(n)$。

证明:

$n = 1$ 时,显然成立;

否则按照定义,将 $d$ 分解后质因子最大幂次超过 $1$ 的不作考虑($0$ 对答案显然没有影响);

那么,剩下的需要考虑的 $d$,就相当于从 $n$ 的各个质因子中取出一部分任意组合。(特别地,将 $d = 1$ 视作取出 $0$ 个质因子)

例如当 $n = 12$ 时,对答案有影响的 $d$,只由 $1$ 和 $2, 3$ 这两个质因子任意组合而成。(此处 $d$ 可等于 $1, 2, 3, 6$,其中 $6 = 2 \times 3$)

从 $w(n)$ 个质因子中取出 $i$ 个,方案数显然是 $C_{w(n)}^i$;对答案的影响,就再乘上 $(-1)^i$ 即可。

于是式子变成了这样:

$$
\sum_{d|n} \mu(d) = \sum_{i = 0}^{w(n)} C^i_{w(n)} (-1)^i
$$

看起来是不是有点眼熟?回顾一下二项式定理:

$$
(a + b)^n = \sum_{i = 0}^n C^i_n a^i b^{n - i}
$$

于是将上式乘上 $1^{w(n) - i}$,则可化为:

$$
\sum_{i = 0}^{w(n)} C^i_{w(n)} (-1)^i 1^{w(n) - i} = (-1 + 1)^{w(n)} = 0
$$

至此得证。

现在有一个问题:这个式子证出来有什么用呢?别急。

这时定义函数 $1(n)$,无论 $n$ 为何值,函数值都为 $1$。

显然,其为完全积性函数,并且对于任意函数 $f$,显然都有以下式子成立:

$$
(1 \ast f)(n) = \sum_{d|n} f(d)
$$

也就是说:

$$
\mu \ast 1 = \sum_{d|n} \mu(d) = \epsilon
$$

即 $\mu$ 与 $1$ 互为逆函数。

感性想想都可以知道,与 $1$ 这种函数互逆,一定会有一些特殊的性质,这也就是构造这么一个奇怪函数的理由

更新:我并不知道莫比乌斯函数和狄利克雷卷积的先后关系,若是 $\text{dalao}$ 知道可以顺便说一下历史- -

然后,这里可以再给出一个神奇的东西:

定义函数 $Id(n) = n$,即函数值等于自变量值,你会发现:

$$
\varphi \ast 1 = Id \\
\mu \ast Id = \varphi
$$

那么接下来,回到正题--

莫比乌斯反演

直接给出具体内容:

$$
f(n) = \sum_{d|n} g(d) \tag 1
$$

$$
g(n) = \sum_{d|n} \mu(d) f(\frac n d) \tag 2
$$

并且其逆命题也成立。

证明:

$(1)$ 式可转化为 $f = 1 \ast g$,$(2)$ 式可转化为 $g = \mu \ast f$。

将 $(1)$ 式两边同卷上 $\mu$:

$$
f \ast \mu = \mu \ast 1 \ast g
$$

发现 $\mu \ast 1 = \epsilon$,且 $g \ast \epsilon = g$

则式子变为:

$$
f \ast \mu = g
$$

至此得证。

证明是不是看起来很简单?毕竟在前面学了一大堆东西,这里再证就显得容易很多了- -

讲完了吗?讲完了。

你肯定还是有点迷糊,那么接下来,我们来看一道例题--

例1 $\text{ZAP-Queries}$

题目大意

$T$ 组询问。

对于给定的正整数 $a, b, x$,求出:

$$
\sum_{i = 1}^a \sum_{j = 1}^b [(i, j) = x]
$$

$1 \le x \le a, b \le 5 \times 10^4$,$T \le 5 \times 10^4$。

分析

朴素算法显然 $O(n^2 \text{log} n)$。(这里 $n$ 和 $a, b$ 同阶,且带上了 $\text{gcd}$ 的 $\text{log}$)

怎么把我们所学的莫比乌斯反演的知识应用上去呢?

观察一下题目所要求的式子,由于 $(i, j) \not = x$ 的情况对答案无影响,不妨将枚举的 $i, j$ 的意义从“具体数字”变为“是 $x$ 的几倍”。

这样就可以保证 $(ix, jx) = x$, 于是式子变为这样:

$$
\sum_{i = 1}^{\lfloor \frac a x \rfloor} \sum_{j = 1}^{\lfloor \frac b x \rfloor} [(i, j) = 1]
$$

这时候,式子中出现了一个有意思的东西:$[(i, j) = 1]$

这跟单位元 $\epsilon(n) = [n = 1]$ 的样子不是一模一样吗?

那么开始化式子:

$$
\begin{aligned}
& \sum_{i = 1}^{\lfloor \frac a x \rfloor} \sum_{j = 1}^{\lfloor \frac b x \rfloor} [(i, j) = 1] \\
=& \sum_{i = 1}^{\lfloor \frac a x \rfloor} \sum_{j = 1}^{\lfloor \frac b x \rfloor} \epsilon((i, j)) \\
=& \sum_{i = 1}^{\lfloor \frac a x \rfloor} \sum_{j = 1}^{\lfloor \frac b x \rfloor} \sum_{d|(i, j)} \mu(d)
\end{aligned}
$$

由 $d|(i, j)$,可知 $d|i$ 且 $d|j$。那么我们可以考虑更换枚举顺序,同时再次更改 $i, j$ 的意义。

先枚举 $d$,再枚举 $i, j$,此时 $i, j$ 的意义再次变为:“是 $xd$ 的几倍”。

于是式子变成这样:

$$
\begin{aligned}
& \sum_d \mu(d) \sum_{i = 1}^{\lfloor \frac a {xd} \rfloor} \sum_{j = 1}^{\lfloor \frac b {xd} \rfloor} 1 \\
=& \sum_d \mu(d) \lfloor \frac a {xd} \rfloor \lfloor \frac b {xd} \rfloor
\end{aligned}
$$

至此,式子就全部化完了,回答询问时间已经从 $O(n^2 \text{log} n)$ 降为了 $O(n)$。(实际观察式子,$O(n)$ 也只是极端情况,很多时候跑不到)

但是因为有多组询问,我们可以运用上面所讲的整除分块的方法,将处理询问的时间优化到 $O(\sqrt n)$。

具体而言,$\lfloor \frac a {xd} \rfloor \lfloor \frac b {xd} \rfloor$ 这两个式子分别都会有自己的不同的分块。

也就是说,对于当前位置 $l$,$a, b$ 都分别有其对应位置 $r_a = \lfloor \frac a {\lfloor \frac a l \rfloor} \rfloor, r_b = \lfloor \frac b {\lfloor \frac b l \rfloor} \rfloor$

将 $\lfloor \frac a {xd} \rfloor \lfloor \frac b {xd} \rfloor$ 这两个相乘的式子视作整体,那么只有取 $r_a, r_b$ 中最小的(定义为 $r$),才能保证 $[l, r]$ 中 $\lfloor \frac a {xd} \rfloor \lfloor \frac b {xd} \rfloor$ 全部相等

既然 $\lfloor \frac a {xd} \rfloor \lfloor \frac b {xd} \rfloor$ 已经全部相等,$\mu(d)$ 用一个简单的前缀和累计一下就可以了。

但是这里再次牵扯出来一个问题:如何快速求出 $\mu$?

因为 $\mu$ 是积性函数,所以我们稍稍改变一下以前学过的线性筛素数的方法,就可以在线性时间内筛出所有 $\mu(i)$ 的值了。

都学莫比乌斯反演了你不要跟我讲你不会线性筛

(其实有比线性筛更优秀的做法,等我学了再补吧233)

具体而言,若当前数是质数,那么 $\mu$ 值为 $-1$;

设用来筛其他数的当前数为 $i$,遍历到的当前质数为 $p$,那么在 $p$ 小于 $i$ 的最小质因子时, $\mu(pi) = -\mu(i)$。

为什么?仔细想想,在遍历到最小质因子之前,当前数和所遍历到的质数一定互质(显然,要不然就和最小质因子矛盾了)

也就是说,$w(pi) = w(i) + 1$。所以有了上述式子。

如果 $p$ 大于等于 $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
98
99
100
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-02-16 10:38
* FileName : else.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>
#include <vector>

typedef long long LL;
typedef unsigned int uint;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
register int x = 0;
register char ch;
while (!isdigit(ch = getchar()));
while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
return x;
}

template <typename _INT>
inline void write(_INT x)
{
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 5e4 + 2;

int T, a, b, x;
LL ans;
int mu[maxN], premu[maxN];
bool vis[maxN];
std::vector<int> prim;

inline void Shuffle(int n)
{
premu[1] = mu[1] = 1;
for (register int i = 2; i <= n; ++i)
{
if (!vis[i])
prim.push_back(i), mu[i] = -1;
for (register uint j = 0; j < prim.size() and prim[j] * i <= n; ++j)
{
vis[i * prim[j]] = true;
if (i % prim[j])
mu[i * prim[j]] = -mu[i];
else
break;
}
premu[i] = premu[i - 1] + mu[i];
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("else.in", "r", stdin);
freopen("else.out", "w", stdout);
#endif
T = read(), Shuffle(maxN - 2);
while (T--)
{
a = read(), b = read(), x = read(), ans = 0;
a /= x, b /= x;
for (register int l = 1, r; l <= std::min(a, b); l = r + 1)
{
r = std::min(a / (a / l), b / (b / l));
ans += (premu[r] - premu[l - 1]) * (LL)(a / l) * (b / l);
}
write(ans), putchar('\n');
}
return 0;
}

例2 $\text{YY}$ 的 $\text{GCD}$

题目大意

$T$ 组数据。

给定 $n, m$,求

$$
\sum_{i = 1}^n \sum_{j = 1}^m [(i, j) \in \mathbb P]
$$

其中 $\mathbb P$ 表示质数集合。

$T = 10^4, n, m \le 10^7$。

分析

(这里设 $n \le m$)

判其是否为质数可能不太好搞,那我们直接在外面枚举质数就行。

式子变成这样:

$$
\sum_{p \in \mathbb P} \sum_{i = 1}^n \sum_{j = 1}^m [(i, j) = p]
$$

然后和上一题同理:

$$
\sum_{p \in \mathbb P} \sum_{d} \mu(d) \lfloor \frac{n}{pd} \rfloor \lfloor \frac{m}{pd} \rfloor
$$

然后就可以愉快地做了

然后 T 飞了。复杂度过高,大概是 $O(T |\mathbb P| \sqrt n)$。

对于这种看似最简化的式子,我们需要一个常用的优化技巧:

令 $x = pd$,则 $d = \frac x p$,式子变为:

$$
\sum_{p \in \mathbb P} \sum_{d = 1}^{\lfloor \frac n p \rfloor} \mu(\frac x p) \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor
$$

再次改变枚举顺序,把 $x$ 提到前面来:

$$
\sum_{x = 1}^n \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor \sum_{p \in \mathbb P, p | x} \mu(\frac x p)
$$

可以发现

$$
\sum_{p \in \mathbb P, p | x} \mu(\frac x p)
$$

这玩意是可以预处理的,线性筛完枚举质数,算其对其倍数的贡献就行。

代码:

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
98
99
100
101
102
103
104
105
106
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-02-16 16:13
* FileName : else.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>
#include <bitset>
#include <vector>

typedef long long LL;
typedef unsigned int uint;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
register int x = 0;
register char ch;
while (!isdigit(ch = getchar()));
while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
return x;
}

template <typename _INT>
inline void write(_INT x)
{
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 1e7;

int T, n, m;
LL ans;
int mu[maxN + 1], F[maxN + 1];
std::bitset<maxN + 1> vis;
std::vector<int> prim;

inline void Shuffle()
{
mu[1] = 1, prim.reserve(int(6e5));
for (register int i = 2; i <= maxN; ++i)
{
if (!vis[i])
prim.push_back(i), mu[i] = -1;
for (register uint j = 0; j < prim.size() and i * prim[j] <= maxN; ++j)
{
vis.set(i * prim[j]);
if (i % prim[j])
mu[i * prim[j]] = -mu[i];
else
break;
}
}
for (register uint i = 0; i < prim.size(); ++i)
for (register int j = 1; prim[i] * j <= maxN; ++j)
F[prim[i] * j] += mu[j];
for (register int i = 2; i <= maxN; ++i)
F[i] += F[i - 1];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("else.in", "r", stdin);
freopen("else.out", "w", stdout);
#endif
T = read(), Shuffle();
while (T--)
{
n = read(), m = read(), ans = 0;
if (n > m)
std::swap(n, m);
for (register int l = 1, r; l <= n; l = r + 1)
{
r = std::min(n / (n / l), m / (m / l));
ans += LL(F[r] - F[l - 1]) * (n / l) * (m / l);
}
write(ans), putchar('\n');
}
return 0;
}

$\huge \text{To be continued…}$