[关闭]
@xzyxzy 2018-08-20T23:44:57.000000Z 字数 5952 阅读 1492

莫比乌斯反演

数学

作业部落

评论地址


引用

YYB:http://www.cnblogs.com/cjyyb/p/7953803.html
YL:http://www.cnblogs.com/cjoieryl/p/8250019.html
ZSY:http://www.cnblogs.com/zhoushuyu/p/8186224.html

一、基本内容

《组合数学》P142写了详细内容,这里简单提一下:

Step1 Mobius函数

定义:

定理:

对于任意正整数n,恒有

证明:

的时候很好证明,的如下
首先转化为,
那么对于那么无贡献,推出
个质数中选个(偶数个系数是,由定义得),选个(奇数个系数是,最后的式子就是(组合数公式)

Step2 Mobius反演

形式A


形式B



这里给出形式的证明

证明:


对于每一个,如果说它要被计算到,那么一定存在一个使得
那么就是,被计算的次数是

然后由上面的定理得出当且仅当不为,为,进而

形式同理可证,核心思想是把贡献提出来

Step 3 举个例子

求:

Way 1



那么(中括号内表示成立为否则为

进而

加上数论分块可以完成(数论分块例题

Way 2

由上面的莫比乌斯函数的定理可以知道


所以说

提贡献:把提到前面来

二、题目

1、练基础

2、刷提高

3、变态题

三、做题经验

1、Mobius求解以下问题

[POI2007]ZAP-Queries题解戳我
  求下式(预处理,还有拓展到Visible Lattice Points


Gcd之和题解戳我
  求下式(jzptab要求单次询问题解戳我

Crash的数字表格->单次求下式
  jzptab->单次求下式(题解戳我

Mophues题解戳我/题解戳我
  预处理并单次求下式,表示唯一分解后不同质因子的个数

Code题解戳我
  构造函数单次求下式,为给定的一个数列,

约数个数和题解戳我【自己写的】
  预处理并单次询问处理下式,的约数个数详见引理

YY的GCD题解戳我
  预处理并单次询问处理下式


Hillan and the girl题解戳我
  预处理并单次询问

于神之怒加强版题解戳我
  预处理并单次询问

数字表格题解戳我
  预处理并且单次询问,其中表示斐波那契数列第i项,

2、小套路

只会用到所以筛的时候可以不用筛到(助力冲榜)
数论分块套路(当数论分块会比较麻烦的时候可以用



提贡献套路(换元思想)

Code
线性筛积性函数积性函数与线性筛

3、注意事项

数据范围大的时候注意随时取模!!
有时候卡空间/时间,那么能用尽量随时

4、引理

  令
  那么
  
  

  表示的约数个数,如
  任意的约数可以表示为
  如果,可以令表示的约数是,但是我们可以发现当的时候就已经统计过这个约数了,再不懂可以手玩
  (Upd2018.8.15:公式写错了已更正 @Tyher)

有关原创文章

线性筛
<约数个数和>题解
<安师大sanrd>题解

Code

  1. void Mobius()
  2. {
  3. mu[1]=1;ispri[1]=1;
  4. for(int i=2;i<=n;i++)
  5. {
  6. if(!ispri[i]) {pri[++tot]=i;mu[i]=-1;}
  7. for(int j=1;j<=tot&&i*pri[j]<=n;j++)
  8. {
  9. ispri[i*pri[j]]=1;
  10. if(i%pri[j])mu[i*pri[j]]=-mu[i];
  11. else break;
  12. }
  13. }
  14. for(int i=1;i<=n;i++)s[i]=s[i-1]+mu[i];
  15. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注