前言
莫比乌斯反演应该是比较难的一类数论题了.
关于它的许多性质, 我也不怎么会证明 (毕竟我数学差得要命).
学习这个算法时, 在别人的博客中看到一句十分经典的话, 在此特将其摘录如下:
\(Excerpt\)
那些各种各样的性质与定理, 大多是前人几年甚至几十年才得出来的, 哪里是你几天就能理解并证明的.
莫比乌斯函数 \(\mu\)
莫比乌斯反演中最重要的自然就是 莫比乌斯函数 \(\mu\) 了.
定义
对于一个正整数 \(d\),\(\mu(d)\) 的定义如下:
\[\mu(d)=\begin{cases}1&d=1\\(-1)^k&d=\prod_{i=1}^kp_i 且 p_i 为互不相同的质数 \\0&d 含有某个指数 \ ge2 的质因子 \ end{cases}\]
性质
其实, 莫比乌斯函数是一个非常有趣的函数, 它有许多我不会证明的很有趣的性质.
比如,\(\sum_{d|n}\mu(d)=\begin{cases}1&n=1\\0&n>1\end{cases}\), 就是一个很常用的性质.
再比如, 对于任意正整数 \(n\),\(\sum_{d|n}\frac {\mu(d)}d=\frac{\phi(n)}n\), 这个性质就十分复杂了, 把欧拉函数也扯了进来 (毕竟这不是本博客的重点内容).
求莫比乌斯函数
我们可以通过线性筛来求莫比乌斯函数, 代码如下:
- class Class_Mobius// 莫比乌斯反演
- {
- private:
- int Prime_cnt,mu[N+5],Prime[N+5];bool IsNotPrime[N+5];
- public:
- LL sum[N+5];
- Class_Mobius()// 预处理
- {
- register int i,j;
- for(mu[1]=1,i=2;i<=N;++i)// 求出莫比乌斯函数, 首先预处理 mu[1]=1
- {
- if(!IsNotPrime[i]) Prime[++Prime_cnt]=i,mu[i]=-1;// 如果当前数是质数, 则说明它由一个质因子组成, 因此 mu[i]=(-1)^1=-1
- for(j=1;j<=Prime_cnt&&i*Prime[j]<=N;++j)// 筛质数, 求 mu
- if(IsNotPrime[i*Prime[j]]=true,i%Prime[j]) mu[i*Prime[j]]=-mu[i];else break;// 因为 i*Prime[j] 比 i 多一个质因子, 所以 mu[i*Prime[j]]=-mu[i]
- }
- }
- }Mobius;
莫比乌斯反演定理
内容
对于定义于非负整数集合上的两个函数 \(F(n)\) 和 \(f(n)\), 若它们满足 \(F(n)=\sum_{d|n}f(d)\), 则可得 \(f(d)=\sum_{d|n}\mu(d)F(\lfloor\frac nd\rfloor)\).
证明
我们可以通过定义来对其进行证明 (由于我不会, 请自行脑补这一过程).
其他
实际上, 莫比乌斯反演还有一种更常见的形式:
对于定义于非负整数集合上的两个函数 \(F(n)\) 和 \(f(n)\), 若它们满足 \(F(n)=\sum_{n|d}f(d)\)(注意, 请仔细看这个式子, 它与上面那个式子长得不一样), 则可得 \(f(d)=\sum_{n|d}\mu(\frac dn)F(d)\), 其实也是同理的.
例题
推荐几道莫比乌斯反演的例题吧:
例题 1: [洛谷 2257] YY 的 GCD
例题 2: [BZOJ3994] [SDOI2015] 约数个数和
来源: http://www.bubuko.com/infodetail-2824938.html