【狄利克雷卷积】
-
定义
f
,
g
两个函数的狄利克雷卷积
(
∗
)
运算为：
(
f
∗
g
)
(
n
)
=
∑
d
|
n
f
(
d
)
g
(
n
d
)
-
狄利克雷卷积的性质：
-
交换律：
f
∗
g
=
g
∗
f
-
结合律：
(
f
∗
g
)
∗
h
=
f
∗
(
g
∗
h
)
-
分配率：
f
∗
(
g
+
h
)
=
f
∗
g
+
f
∗
h
-
单位元：
f
∗
e
=
e
∗
f
-
若
f
,
g
均为积性函数，则
f
∗
g
也为积性函数。
-
交换律：
-
常见的狄利克雷卷积：
-
d
(
n
)
=
∑
d
|
n
1
即
d
=
1
∗
1
-
σ
(
n
)
=
∑
d
|
n
d
即
σ
=
d
∗
1
-
φ
(
n
)
=
∑
d
|
n
μ
(
d
)
n
d
即
φ
=
μ
∗
I
d
证明：
因
为
I
d
(
n
)
=
∑
i
=
1
n
∑
j
=
1
n
[
g
c
d
(
i
,
n
)
=
=
j
]
则
I
d
(
n
)
=
∑
j
|
n
∑
i
=
1
⌊
n
j
⌋
[
g
c
d
(
i
,
n
j
)
=
=
1
]
那
么
I
d
(
n
)
=
∑
j
|
n
φ
(
n
j
)
即
I
d
=
1
∗
φ
根
据
反
演
可
得
φ
=
μ
∗
I
d
-
ϵ
(
n
)
=
∑
d
|
n
μ
(
d
)
即
ϵ
=
μ
∗
1
证明：
令
k
表
示
n
的
不
同
的
质
因
子
数
，
可
得
∑
d
|
n
μ
(
d
)
=
∑
i
=
0
k
(
−
1
)
i
(
k
i
)
通
过
二
项
式
展
开
可
得
(
x
+
y
)
k
=
∑
i
=
0
k
x
i
y
k
−
i
(
k
i
)
将
x
=
1
,
y
=
−
1
代
入
可
得
∑
i
=
0
k
(
−
1
)
i
(
k
i
)
=
(
1
−
1
)
k
=
0
k
所
以
只
有
当
k
=
0
(
即
n
=
1
)
时
，
∑
d
|
n
μ
(
d
)
=
1
，
否
则
∑
d
|
n
μ
(
d
)
=
0
所
以
ϵ
(
n
)
=
∑
d
|
n
μ
(
d
)
-