【OI之路】11更高级数论-3莫比乌斯反演

前方高能!请先学好线性筛

update:2017.11.27 莫比乌斯函数能使用线性筛获得是因为它是一个积性函数
(注意并不是完全积性函数),
而一个质数与任何数必定互质,所以能用后文介绍的方法求得。

注意:本文提到的除法运算都是向下取整,因为小数部分完全没有意义。

莫比乌斯反演,需要使用到一个名为莫比乌斯函数的东东
即所谓 $\mu$(mu)函数

$\mu$函数的运用

我们先不解释$\mu$(mu)函数,而是假设我们已经求得它,并尝试利用它做题
例题:GCD-莫比乌斯1
求数对(x,y)满足$gcd(x,y)=k$,其中$x\leq b,y\leq d$
并且(1,2)和(2,1)算一对

解:
先简化问题为$gcd(x,y)=1$,其中$x\leq b/k,y\leq d/k$
为方便表示设n=b/k,m=d/k

设f(t)为满足gcd(x,y)=t的对数,
其中$x\leq n,y\leq m$,本题相当于求f(1)

由于直接求f(t)较困难,考虑另一个函数
F(d)为满足gcd(x,y)%d=0的对数,
其中$x\leq n,y\leq m$,
又因为两个数的最大公约数不可能超过任何一个数,
所以$t和d \leq min(x,y)$ 当然$ t和d \leq min(n,m)$
易知$F(d)=\frac{n}{d} \times \frac{m}{d}$

算了还是证明一下这个“易知”吧
x可以是$d或2d或3d\ldots一直到ad(\leq n)$,共$\frac{n}{d}个$
y也可以是$d或2d或3d\ldots一直到bd(\leq m)$,共$\frac{m}{d}个$
所以就是$\frac{n}{d} \times \frac{m}{d}$

所以,F(d)可以轻松地算出,接下来就是要从F(d)反演出f(t)
他们有如下关系(属于“倍数”类,另一种是约数类)
$ F(d)=\sum f(t) 要求满足d|t且t\leq min(n,m) $
通过莫比乌斯反演的倍数版公式转化为
(原理是运用容斥,具体证明一会再讲)
$ f(t)=\sum \mu(\frac{d}{t}) \times F(d) 要求满足t|d且d\leq min(n,m) $

G(a,b)为当n=a,m=b时的f(1)
这道题的最后答案就是G(n,m)-G(n,n)/2 (假设n<=m)
原因可以看这幅图(转载):

也就是右边的公共部分只能取一半,所以减去另外不需要的一半。

$\mu$函数的计算和证明

显然,$\mu$函数可以理解为一种针对F(d)的系数值
为了与刚才的题目运用的公式不同从而让读者有更广泛的认知以及便于证明
【因为倍数版太长啦!所以例题是倍数版,但我们计算和证明用约数版】
约数版公式:
$ f(t)=\sum \mu(\frac{t}{d}) \times F(d) 要求满足d|t且d\leq min(n,m) $

额$\mu$这个符号比较麻烦,下文我可能用U表示相同的意义

$\mu$有以下性质(有原因,一会再解释):
$\mu(x)=1$ 当且仅当x能够分解成偶数个不同质数的乘积(其中1不能被分解,所以1的分解出的质数个数是0,所以U[1]=1)
$\mu(x)=-1$ 当且仅当x能够分解成奇数个不同质数的乘积
$\mu(x)=0$ 除开(2),(3)的其他情况

看上面关于$\mu$的定义可能有点看晕了,通俗一点的说:
对于一个 x ,分解因式过后有 $x=(p_1^{e_1})(p_2^{e_2})…(p_r^{e_r})$
$如果e_i中(1<=i<=r)有一个数大于1 那么 U[x]=0 $
$不然的话 U[x]=(-1)^r$

来几个栗子
U[1]=1; 定义
U[2]=-1;分解式 $2=2$
U[6]=1; 分解式 $6=2\times 3$
U[9]=0; 分解式 $9=3^2$
U[12]=0;分解式 $12=2^2\times 3$

设H(d,t)是计算f(t)时F(d)的系数
然后从栗子中找规律
$F(8)=H(8,8)\times G(8)+H(4,8)\times G(4)+H(2,8)\times G(2)+H(1,8)\times G(1) $
举栗子自己推算,
可以发现$H(d,t)=H(1,\frac{t}{d})$,
于是我们把H的第一个元素略去,简写为H(x),也就是如今的$\mu(x)$
【这就是为什么上面的公式,$\mu$这个系数,下标是个这样的分数了】

好了性质讲完了,那为什么有这样的性质呢?
我们边讲 计算,边证明这些性质【所以先忘记性质】

首先需要明确2点!
一是 F(x)中,一定包含一个f(1),因为 1|x
二是 f(1)=F(1) 【显而易见】

接下来从多种角度尝试,具体推算过程就略过了,自己动手试试吧~
(0).如果 x=1,因为 f(1)=F(1) 所以 $\mu(1)=1$
(1).假设 x 是一个 质数 ,易知 $\mu(x)=-1$
(2).假设 x 可以写成2个不同质数的乘积,易知 $\mu(x)=1$
(3).假设 x 可以写成3个不同质数的乘积,易知 $\mu(x)=-1$
(4).假设 x 可以写成r个不同质数的乘积,易知 $\mu(x)=(-1)^r $
(5).假设 x 可以写成一个质数的平方$ x=p^2 $,易知 $\mu(x)=0$
(6).假设 x 可以写成一个质数的次幂$ x=p^g $,易知 $\mu(x)=0$
总而言之,$\mu$函数的求法也就是其性质了
所以可以用线性筛素数来预处理出莫比乌斯函数
【据说莫比乌斯函数在任何题目都不会变,变化的只是F(x)和f(x)的定义】

那么我写这一段的原因在于,不要只是单纯地记住这个性质,
而是应该试图理解这是怎么来的。

$\mu$函数的特性

  1. 积性函数
  2. 当n>1,$ \sum_{d|n} \mu(d)=0 $,当n=1则是1
  3. $\sum_{d|n} \frac{\mu(d)}{d}=\frac{\varphi(n)}{n}$

公式

倍数和公式
$F(d)=\sum f(t) 要求满足d|t $
$f(t)=\sum \mu(\frac{d}{t})\times F(d) 要求满足t|d$
约数和公式
$F(d)=\sum f(t) 要求满足t|d $
$f(t)=\sum \mu(d)\times F(\frac{t}{d}) 要求满足d|t$ (网上好像常见这个)
$f(t)=\sum \mu(\frac{t}{d})\times F(d) 要求满足d|t$ (其实这个也是等效的)

莫比乌斯所有题目

Tag-莫比乌斯反演

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/d81d.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%