对于一个函数
f
(
x
)
f(x), 如果满足对于任意的 $(a, b) |
g
c
d
(
a
,
b
)
1
,
a
∈
Z
,
b
∈
Z
gcd(a,b)=1,a∈Z,b∈Z,
f
(
a
b
)
f
(
a
)
f
(
b
)
f(ab)=f(a)f(b), 那么称这个函数为积性函数(数论函数)
特别地, 如果对于所有的
(
a
,
b
)
∣
a
∈
Z
,
b
∈
Z
(a,b)∣a∈Z,b∈Z 都有
f
(
a
b
)
f
(
a
)
f
(
b
)
f(ab)=f(a)f(b) 的话, 函数
f
f 被称为 完全积性函数(完全数论函数)
二者区别在于是否要求两整数互质
常见的积性函数
常数函数:
1
(
n
)
1
1(n)=1 (完全积性函数)
单位函数:
ε
(
n
)
[
n
1
]
ε(n)=[n=1][1] (完全积性函数)
恒等函数:
i
d
k
(
n
)
n
k
id
k
(n)=n
k
, 这里通常所说的恒等函数当
k
k 取
1
1, 即
i
d
1
id
1
, 一般记作
i
d
id (完全积性函数)
除数函数:
σ
k
(
n
)
∑
d
∣
n
d
k
σ
k
(n)=
d∣n
∑
d
k
, 通常我们把
σ
1
(
n
)
σ
1
(n) 记作
σ
(
n
)
σ(n) 或者
d
(
n
)
d(n), 实际意义是
n
n 的因数和
欧拉函数:
φ
(
n
)
∑
i
1
n
[
g
c
d
(
i
,
n
)
1
]
φ(n)=
i=1
∑
n
[gcd(i,n)=1], 即统计小于等于
n
n 的数中与
n
n 互质的数的个数
莫比乌斯函数: 简单说来: 当
n
n 等于
1
1 时,
μ
(
n
)
1
μ(n)=1; 否则, 当
n
n 的素数分解中有非一次的素因子时
μ
(
n
)
0
μ(n)=0; 否则, 当
n
n 有奇数个素因子时,
μ
(
n
)
−
1
μ(n)=−1; 否则,
μ
(
n
)
1
μ(n)=1. 形式化地
μ
(
n
)
{
1
,
n
1
0
,
n
有平方素因子
(
−
1
)
k
,
n
p
1
p
2
⋯
p
k
（
k
个不同素因子）
μ(n)=
⎩
⎨
⎧
1,
0,
(−1)
k
,
n=1
n 有平方素因子
n=p
1
p
2
⋯p
k
（k 个不同素因子）
推荐读者自己证明所有的积性函数的 积性
狄利克雷卷积
对于积性函数
f
f 和
g
g, 它们的卷积
f
∗
g
f∗g 满足这样一个关系式:
(
f
∗
g
)
(
n
)
∑
d
∣
n
f
(
n
)
g
(
n
d
)
(f∗g)(n)=
d∣n
∑
f(n)g(
d
n
)
这里有一个良好的性质, 因为因数是成对出现的, 所以积性函数卷积显然满足交换律(当然卷积本身就满足交换律), 也就是说我们有
(
f
∗
g
)
(
n
)
∑
d
∣
n
f
(
n
)
g
(
n
d
)
∑
d
∣
n
g
(
n
)
f
(
n
d
)
(f∗g)(n)=
d∣n
∑
f(n)g(
d
n
)=
d∣n
∑
g(n)f(
d
n
)
莫比乌斯反演
莫比乌斯反演就是利用莫比乌斯函数和狄利克雷卷积将一些难以直接计算的量转化为便于计算的量从而降低复杂度
最常用的是下列恒等式
∑
d
∣
n
μ
(
d
)
[
n
1
]
ε
(
n
)
d∣n
∑
μ(d)=[n=1]=ε(n)
Proof
根据狄利克雷卷积, 我们还可以知道
ε
1
∗
μ
ε=1∗μ
以这一个最常见的莫比乌斯反演作为例子, 读者理解后应当可以推出大多其它的反演式子
求解莫比乌斯函数
根据定义我们显然可以枚举出来质因数然后 check, 是
O
(
n
)
O(
n
) 的, 但当我们要求出很多数的莫比乌斯函数的时候这个复杂度就有些难以接受了
为了解决这个问题, 我们来思考如何确定
n
n 的莫比乌斯函数的取值, 因为这是一个积性函数, 且对于一个质数
p
p,
μ
(
p
)
μ§ 一定等于
−
1
−1. 所以当
n
n 为合数时, 我们可以枚举小于
n
n 的质数
p
p, 然后分为两类:
p
∣
n
p∣n, 这个时候的
μ
(
p
n
)
μ(pn) 一定含有一个
p
2
p
2
的因子项, 所以
μ
(
p
n
)
0
μ(pn)=0
p
∤
n
p∤n, 这个时候
μ
(
p
n
)
μ(pn) 相当于在
n
n 的基础上添加了一个新的因子
p
p, 由积性函数定义,
μ
(
p
n
)
μ
(
p
)
×
μ
(
n
)
μ(pn)=μ§×μ(n), 由我们刚才所讲的
μ
(
p
)
μ§ 一定等于
−
1
−1, 我们有
μ
(
p
n
)
−
1
μ
(
n
)
−
μ
(
n
)
μ(pn)=−1μ(n)=−μ(n)
我们发现这个过程很类似于筛法, 所以我们可以使用埃氏筛
O
(
n
l
n
l
n
n
)
O(n ln ln n) 的做
但事实上还可以优化, 如果我们使用线性筛, 则可以做到
O
(
n
)
O(n). 简要介绍一下线性筛的思想, 只用一个合数最小的质因子来筛除这个数, 具体可以看代码然后感性理解或者 OI-Wiki
而几乎在所有的本文提到的数论函数中, 线性筛其实是好写于埃氏筛的, 通常表现在于我们只需要找到一个最小的
n
n 的质因数
p
p, 这个目标是与线性筛相同的
这里贴一份代码
// ========= Made By BilllIlllly =========
std::vector is_prime;
std::vector mu;
std::vector primes;
void sieve(int n) {
is_prime.assign(n + 1, true);
mu.assign(n + 1, 0);
is_prime[1] = false; // 如果你认为 1 是质数, 那你也可以去掉这一行 mu[1] = 1; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { primes.emplace_back(i); mu[i] = -1; } for (int p : primes) { if (i * p > n) break; is_prime[i * p] = false; if (i % p == 0) { mu[i * p] = 0; break; } mu[i * p] = -mu[i]; } }}
例题
互质数对个数
这是莫比乌斯反演最经(jian)典(dan)的一道例题, 虽然好像并没有找到被出成题的版本
给定一个正整数
n
n, 求
∑
i
1
n
∑
j
1
n
[
g
c
d
(
i
,
j
)
1
]
i=1
∑
n
j=1
∑
n
[gcd(i,j)=1], 简单来说就是在
[
1
,
n
]
[1,n] 中有多少个互质的整数对
朴素做法
枚举
i
,
j
i,j, 然后求gcd, 是
O
(
n
2
l
o
g
n
)
O(n
2
logn) 的, 不能接受
反演做法
我们发现
[
g
c
d
(
i
,
j
)
1
]
[gcd(i,j)=1] 可以写成
ε
(
g
c
d
(
i
,
j
)
)
ε(gcd(i,j)), 所以原式等于
∑
i
1
n
∑
j
1
n
ε
(
g
c
d
(
i
,
j
)
)
i=1
∑
n
j=1
∑
n
ε(gcd(i,j))
由莫比乌斯反演, 原式等于
∑
i
1
n
∑
j
1
n
∑
d
∣
g
c
d
(
i
,
j
)
μ
(
i
)
i=1
∑
n
j=1
∑
n
d∣gcd(i,j)
∑
μ(i)
∑
i
1
n
∑
j
1
n
∑
d
∣
i
d
∣
j
μ
(
i
)
i=1
∑
n
j=1
∑
n
d∣i
d∣j
∑
μ(i)
考虑从枚举
(
i
,
j
)
(i,j) 变为枚举
d
d, 原式等于
∑
d
1
n
∑
d
∣
i
n
∑
d
∣
j
n
μ
(
d
)
d=1
∑
n
d∣i
∑
n
d∣j
∑
n
μ(d)
这里需要注意的是, 虽然我们写的是
d
∣
i
,
d
∣
j
d∣i,d∣j, 但事实上这两个求和的求和记号分别是
i
,
j
i,j, 简单来说我们实际上实在令
i
,
j
i,j 是
d
d 的倍数
这个时候发现原式的
μ
(
d
)
μ(d) 和
i
,
j
i,j 无关, 所以我们直接交换求和次序, 原式等于
∑
d
1
n
μ
(
d
)
∑
d
∣
i
n
∑
d
∣
j
n
1
d=1
∑
n
μ(d)
d∣i
∑
n
d∣j
∑
n
1
最后我们考虑这里的后面两个
∑
∑ 怎么处理, 事实上,
i
,
j
i,j 的取值数量为
n
n 中的
d
d 的倍数的数量, 也就是
⌊
n
d
⌋
⌊
d
n
⌋, 所以总共有
⌊
n
d
⌋
2
⌊
d
n
⌋
2
个取值, 原式就终于被我们化为了
∑
d
1
n
(
μ
(
d
)
⌊
n
d
⌋
2
)
d=1
∑
n
(μ(d)⌊
d
n
⌋
2
)
我们分析这个式子
μ
(
d
)
μ(d) 事实上是可以通过预处理达到
O
(
1
)
O(1) 的, 预处理的复杂度最常见的可以线性筛(前文讲过); 或者如果需求更快, 可以用杜教筛; 想要更快, 可以用洲阁筛或者Min-25筛(当然我只会线性筛).
⌊
n
d
⌋
2
⌊
d
n
⌋
2
显然可以
O
(
1
)
O(1) 每次的求出
综上, 通过线性筛预处理, 我们 至少 可以做到
O
(
n
)
O(n).
优化：整除分块
现在具体再来讲一下莫比乌斯反演最严厉的父亲——整除分块。
预处理出
μ
μ 的前缀和，利用整除分块（也叫数论分块），我们可以把单次查询的复杂度降到
O
(
n
)
O(
n
)！
观察式子
⌊
n
d
⌋
⌊
d
n
⌋，当
d
d 在
[
1
,
n
]
[1,n] 内变化时，这个式子的取值其实只有
O
(
n
)
O(
n
) 种。
为什么呢？
当
d
≤
n
d≤
n
时，
⌊
n
d
⌋
⌊
d
n
⌋ 显然最多只有
n
n
种取值。
当
d
n
d>
n
时，
⌊
n
d
⌋
≤
n
⌊
d
n
⌋≤
n
，所以也最多只有
n
n
种取值。
综上，取值总数不超过
2
n
2
n
。而且，对于同一个取值
k
⌊
n
d
⌋
k=⌊
d
n
⌋，满足条件的
d
d 一定是一段连续的区间
[
l
,
r
]
[l,r]。
这个区间的右端点
r
r 怎么求呢？
由
k
⌊
n
d
⌋
≤
n
d
k=⌊
d
n
⌋≤
d
n
，可得
d
≤
n
k
d≤
k
n
，所以最大的
d
d 就是
⌊
n
k
⌋
⌊
k
n
⌋。
也就是说，右端点
r
⌊
n
⌊
n
/
l
⌋
⌋
r=⌊
⌊n/l⌋
n
⌋。
这样，我们就可以把
d
d 分成
O
(
n
)
O(
n
) 段，每一段内的
⌊
n
d
⌋
2
⌊
d
n
⌋
2
是相同的，提出来之后，只需要乘上这一段
μ
(
d
)
μ(d) 的和（即前缀和之差）即可。
预处理前缀和
O
(
n
)
O(n)，单次查询
O
(
n
)
O(
n
)。我们将一些问题的复杂度从最初的
O
(
n
2
l
o
g
n
)
O(n
2
logn) 降为了
O
(
n
)
O(
n
)!
YY的GCD
有了整除分块，我们来看一道真正的板子题。
题目大意：给定
N
,
M
N,M，求
∑
i
1
N
∑
j
1
M
[
gcd
(
i
,
j
)
∈
prime
]
i=1
∑
N
j=1
∑
M
[gcd(i,j)∈prime]。多组询问。
推导过程
首先，枚举质数
p
p：
∑
p
∈
prime
∑
i
1
N
∑
j
1
M
[
gcd
(
i
,
j
)
p
]
p∈prime
∑
i=1
∑
N
j=1
∑
M
[gcd(i,j)=p]
把
p
p 除进去：
=
∑
p
∈
prime
∑
i
1
⌊
N
/
p
⌋
∑
j
1
⌊
M
/
p
⌋
[
gcd
(
i
,
j
)
1
]
p∈prime
∑
i=1
∑
⌊N/p⌋
j=1
∑
⌊M/p⌋
[gcd(i,j)=1]
使用基本反演公式
[
gcd
(
i
,
j
)
1
]
∑
d
∣
gcd
(
i
,
j
)
μ
(
d
)
[gcd(i,j)=1]=∑
d∣gcd(i,j)
μ(d)：
=
∑
p
∈
prime
∑
i
1
⌊
N
/
p
⌋
∑
j
1
⌊
M
/
p
⌋
∑
d
∣
gcd
(
i
,
j
)
μ
(
d
)
p∈prime
∑
i=1
∑
⌊N/p⌋
j=1
∑
⌊M/p⌋
d∣gcd(i,j)
∑
μ(d)
把
d
d 提出来先枚举：
=
∑
p
∈
prime
∑
d
1
min
(
⌊
N
/
p
⌋
,
⌊
M
/
p
⌋
)
μ
(
d
)
⌊
N
p
d
⌋
⌊
M
p
d
⌋
p∈prime
∑
d=1
∑
min(⌊N/p⌋,⌊M/p⌋)
μ(d)⌊
pd
N
⌋⌊
pd
M
⌋
这里令
T
p
d
T=pd，则
d
T
/
p
d=T/p。我们改变枚举顺序，先枚举
T
T：
=
∑
T
1
min
(
N
,
M
)
⌊
N
T
⌋
⌊
M
T
⌋
∑
p
∣
T
,
p
∈
prime
μ
(
T
p
)
T=1
∑
min(N,M)
⌊
T
N
⌋⌊
T
M
⌋
p∣T,p∈prime
∑
μ(
p
T
)
令
f
(
T
)
∑
p
∣
T
,
p
∈
prime
μ
(
T
p
)
f(T)=
p∣T,p∈prime
∑
μ(
p
T
)。
那么原式 =
∑
T
1
min
(
N
,
M
)
⌊
N
T
⌋
⌊
M
T
⌋
f
(
T
)
T=1
∑
min(N,M)
⌊
T
N
⌋⌊
T
M
⌋f(T)
对于
f
(
T
)
f(T)，我们可以用类似埃氏筛的方法在
O
(
N
log
N
)
O(NlogN) 内预处理出来，并求出前缀和
S
(
T
)
∑
i
1
T
f
(
i
)
S(T)=∑
i=1
T
f(i)。
cpp
// 预处理 f(T)
for (int i = 1; i <= MAXN; ++i) {
if (is_prime[i]) {
for (int j = 1; i * j <= MAXN; ++j) {
f[i * j] += mu[j];
}
}
}
// 求前缀和
for (int i = 1; i <= MAXN; ++i) {
sum_f[i] = sum_f[i - 1] + f[i];
}
