浅谈莫比乌斯反演

浅谈莫比乌斯反演

那些各种各样的性质与定理,大多是前人几年甚至几十年才得出来的,哪里是你几天就能理解并证明的。

简介

莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$,如果很难直接求出它的值,而容易求出其倍数和或约数和 $g(n)$,那么可以通过莫比乌斯反演简化运算,求得 $f(n)$ 的值。

–OI Wiki

莫比乌斯函数

定义

$$\mu(d)=\begin{cases}1&d=1\\(-1)^k&d=\prod_{i=1}^kp_i\text{且}p_i\text{为互不相同的质数}\\0&d\text{含有平方因子}\end{cases}$$

令 $n=\prod_{i=1}^k p_i^{c_i}$,其中 $p_i$ 为质因子,$c_i\ge 1$。

  1. 当 $n=1$ 时,$\mu(n)=1$。
  2. 当 $n\not = 1$ 时:
  • 若 $\exists i\in[1,k],c_i>1$,那么 $\mu(n)=1$。
  • 若 $\forall i \in [1,k],c_i=1$,那么 $\mu(n)=(-1)^k$。

性质

莫比乌斯函数是积性函数,并且有以下性质:

  1. $$\sum\limits_{d|n}\mu(d)=\begin{cases}1 & n=1\\0 & n\not = 1\end{cases}$$
  2. $$\sum\limits_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}$$

求法

由于莫比乌斯函数是典型的积性函数,所以也可以用欧拉筛筛出来。

I void GM(){
    RI i,j;for(mu[1]=1,i=2;i<N;i++) for(!v[i]&&(mu[p[++tot]=i]=-1,0),j=1;j<=tot&&i*p[j]<N;j++)
    if(v[i*p[j]]=1,i%p[j]) mu[i*p[j]]=-mu[i];else break ;
    for(i=1;i<N;i++) mu[i]+=mu[i-1];
}

莫比乌斯反演

令 $F(n)$ 与 $f(n)$ 为定义在非负整数域上的两个函数,且他们之间满足 $$F(n)=\sum\limits_{d|n}f(d)$$。

那么我们有 $$f(n)=\sum\limits_{d|n}\mu(d)F(\lfloor \frac{n}{d}\rfloor)$$

这就是莫比乌斯反演定理,它还有另外一种形式:

如果 $$F(n)=\sum\limits_{n|d}f(d)$$

那么我们有 $$f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})F(d)$$

例题

基础题

  • P2522 [HAOI2011]Problem b
  • P3455 [POI2007]ZAP-Queries
  • P2257 YY的GCD

提高题

咕了

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇