1

目录

• 前言
• 莫比乌斯函数
  • 定义
  • 性质
    • 性质一
      • 应用

前言

• 莫比乌斯反演还挺麻烦的，性质与结论比较多。为了巩固自己，于是写下此学习小记。
  

莫比乌斯函数

定义

莫比乌斯函数$mu(n)$定义如下:
设$n=p_1^{q_1}cdot p_2^{q_2}cdots p_k^{q_k}$,其实$p$为素数，则有

mu(n)=egin{cases}
1 & 	ext{$n=1$} \[2ex]
(-1)^k & 	ext{$p_1p_2cdots p_k,forall p_i
ot=p_j$}\[2ex]
0 & 	ext{other}
end{cases}

性质

性质一

莫比乌斯函数是积性函数

mu(ab)=mu(a) cdot mu(a)  ,  aperp b

可以考虑拆分$a,b,ab$的质因数，显然得证

应用

根据这个性质，我们可以在$O(n)$的时间内用线筛求出$[1,n]$的莫比乌斯函数值。

质数的值为-1。一个数为0，当且仅当这个数这个数被一个素数筛了两次。剩余的情况，可以根据$mu(i)=-mu(i)$来更新。

每个数最多被一个最小的素数筛去，故时间复杂度为$O(n)$