当前位置 博文首页 > LZH的博客：积性函数大全（欧拉函数、莫比乌斯反演、杜教筛……
积性函数是OI中的数论题的重要组成部分 （一般都是涉及到各种因数啊，倍数啊，gcd啊
有下面这样一个式子：
∑
i
=
1
n
?
n
i
?
\sum_{i=1}^n \left \lfloor {n \over i}\right \rfloor
i=1∑n??in??
求这样一个东西需要多久？ O ( n ) O(n) O(n)？
仔细观察，我们会发现 ? n i ? \left \lfloor {n \over i}\right \rfloor ?in?? 会有相同的取值。
比如： 18 7 = 18 8 = 18 9 = 2 {18\over 7}={18\over 8}={18\over 9}=2 718?=818?=918?=2
有这样一个结论 ? n i ? \left \lfloor {n \over i}\right \rfloor ?in?? 最多有 2 n 2\sqrt n 2n? 种取值
所以可以 O ( n ) O(\sqrt n) O(n?) 算出答案。
莫比乌斯函数，像这样
μ
(
n
)
\mu(n)
μ(n)
{
μ
(
n
)
=
0
(
n
为
一
个
质
数
平
方
的
倍
数
)
μ
(
n
)
=
(
?
1
)
k
(
n
的
质
因
数
的
个
数
为
k
)
\left\{ \begin{array}{lr} \mu(n)=0 &(n为一个质数平方的倍数)\\ \mu(n)=(-1)^k &(n的质因数的个数为 k)\\ \end{array} \right.
{μ(n)=0μ(n)=(?1)k?(n为一个质数平方的倍数)(n的质因数的个数为k)?
例如
μ
(
1
)
=
1
=
(
?
1
)
0
μ
(
30
)
=
?
1
=
(
?
1
)
3
(
30
=
2
×
3
×
5
)
μ
(
6
)
=
1
=
(
?
1
)
2
(
6
=
2
×
3
)
μ
(
12
)
=
0
(
12
=
2
2
×
3
)
\left. \begin{array}{lr} \mu(1)=1=(-1)^0\\ \mu(30)=-1=(-1)^3 &(30=2\times 3\times 5)\\ \mu(6)=1=(-1)^2 &(6=2\times 3)\\ \mu(12)=0 &(12=2^2\times 3) \end{array} \right.
μ(1)=1=(?1)0μ(30)=?1=(?1)3μ(6)=1=(?1)2μ(12)=0?
