《莫比乌斯反演.ppt》由会员分享，可在线阅读，更多相关《莫比乌斯反演.ppt（27页珍藏版）》请在三一办公上搜索。
1、莫比乌斯反演,吉大附中实验学校 PoPoQQQ,什么是莫比乌斯反演？,介绍这个之前，我们先来看一个函数 根据F(n)的定义，我们显然有：F(1)=f(1)F(2)=f(1)+f(2)F(3)=f(1)+f(3)F(4)=f(1)+f(2)+f(4)F(5)=f(1)+f(5)F(6)=f(1)+f(2)+f(3)+f(6)F(7)=f(1)+f(7)F(8)=f(1)+f(2)+f(4)+f(8),于是我们可以通过F(n)推导出f(n),f(1)=F(1)f(2)=F(2)-F(1)f(3)=F(3)-F(1)f(4)=F(4)-F(2)f(5)=F(5)-F(1)f(6)=F(6)-F(3)
2、-F(2)+F(1)f(7)=F(7)-F(1)f(8)=F(8)-F(4)在推导的过程中我们是否发现了一些规律？,莫比乌斯反演,公式：其中 为莫比乌斯函数，定义如下：(1)若 则(2)若，为互异素数，那么(3)其它情况下,莫比乌斯函数的性质,(1)对于任意正整数n有：证明：当 时显然当 时，将 分解可以得到 在 的所有因子中，值不为零的只有所有质因子次数都为1的因子，其中质因数个数为 个的因子有 个那么显然有：,莫比乌斯函数的性质,只需证明 即可二项式定理：令，代入即可得证。,莫比乌斯函数的性质,(2)对于任意正整数n有：其实没什么用，结论挺好玩的可以记一下只需要令，代入莫比乌斯反演的公式即
3、可至于为什么 就留给大家做思考题了,莫比乌斯函数的性质,(3)积性函数数论上积性函数的定义：积性函数的性质：积性函数的前缀和也是积性函数,莫比乌斯函数的性质,由于莫比乌斯函数是积性函数，因此我们可以通过线性筛来求出莫比乌斯函数的值代码：mu1=1;for(i=2;i=n;i+)if(!not_primei)prime+tot=i;mui=-1;for(j=1;primej*i=n;j+)not_primeprimej*i=1;if(i%primej=0)muprimej*i=0;break;muprimej*i=-mui;,BZOJ 2440 完全平方数,题目大意：求第k个无平方因子数无平方因
4、子数(Square-Free Number)，即分解之后所有质因数的次数都为1的数首先二分答案 问题转化为求1,x之间有多少个无平方因子数根据容斥原理可知 对于sqrt(x)以内所有的质数 有 x以内的无平方因子数=0个质数乘积的平方的倍数的数的数量(1的倍数)-每个质数的平方的倍数的数的数量(9的倍数,25的倍数,.)+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,.)-.,BZOJ 2440 完全平方数,容易发现每个乘积a前面的符号恰好是(例如 故9对答案的贡献为负；，故36对答案的贡献为正)x以内i2的倍数有 个 故有这题和莫比乌斯反演没关系，算是莫比乌斯函数的一个应用
5、吧。,现在我们来证明莫比乌斯反演定理,证明：这里利用到了 这条性质形式二：证明同理 一般要用到的都是这种形式,有了这个定理，我们能干什么？,对于一些函数f(n)，如果我们很难直接求出它的值，而容易求出倍数和或约数和F(n)，那么我们可以通过莫比乌斯反演来求得f(n)的值例：f(n)表示某一范围内(x,y)=n的数对的数量，F(n)表示某一范围内n|(x,y)的数对的数量那么直接求f(n)并不是很好求，而F(n)求起来相对无脑一些，我们可以通过对F(n)进行莫比乌斯反演来求得f(n)下面用几道例题来为大家讲解一下莫比乌斯反演的好处,BZOJ 2301 Problem b,n次询问，每次询问有多少
6、个数对(x,y)满足a=x=b,c=y=d且gcd(x,y)=kN=5W,1=a=b=5W,1=c=d=5W首先利用容斥原理将一个询问拆分成四个，每次询问有多少个数对(x,y)满足1=x=n,1=y=m且gcd(x,y)=k这个问题等价于询问有多少个数对(x,y)满足1=x=floor(n/k),1=y=floor(m/k)且x与y互质利用NOI2010能量采集中的方法，我们可以得到一个O(nlogn)的算法，但是这显然不能胜任此题的数据范围这时候我们就可以考虑莫比乌斯反演了,BZOJ 2301 Problem b,由于之前的结论，我们可以令f(i)为1=x=n,1=y=m且gcd(x,y)=
7、i的数对(x,y)的个数，F(i)为1=x=n,1=y=m且i|gcd(x,y)的数对(x,y)的个数那么显然有反演后可得枚举原题中k的每一个倍数，我们就可以O(n)时间处理每个询问了但是O(n)还是不能胜任本题的数据范围考虑进一步优化,BZOJ 2301 Problem b,观察式子，发现 最多有 个取值那么 就至多有 个取值枚举这 个取值，对莫比乌斯函数维护一个前缀和，就可以在 时间内出解总时间复杂度枚举除法的取值这种方法在莫比乌斯反演的应用当中非常常用，且代码并不难写不难写？怎么写？,BZOJ 2301 Problem b,if(nm)swap(n,m);for(i=1;i=n;i=la
8、st+1)last=min(n/(n/i),m/(m/i);re+=(n/i)*(m/i)*(sumlast-sumi-1);return re;超级好写不是么？,BZOJ 2820 YGY的GCD,题目大意：求有多少数对(x,y)(1=x=n,1=y=m)满足gcd(x,y)为质数n,m=1000W 数据组数=1W首先我们枚举每一个质数 那么答案就是直接做显然TLE 考虑优化 令，那么有,BZOJ 2820 YGY的GCD,如果能求出 的前缀和，这个问题就能在 时间内出解。只需要暴力枚举每一个质数，去更新这个质数的倍数即可。由 这个结论易知每个质数更新时是均摊 的，而质数个数恰好为故暴力枚举
9、+维护前缀和的时间复杂度即为。,BZOJ 3529 数表,题目大意：令F(i)为i的约数和，q次给定n,m,a,求n,m=105,q=2W,a=109a的限制十分讨厌 我们首先假设没有这个限制令g(i)为1=x=n,1=y=m,gcd(x,y)=i的数对(x,y)的个数那么显然有,BZOJ 3529 数表,F(i)利用线性筛可以在O(n)时间内处理出来 那么就有治好了我多年的公式恐惧症现在我们只要有 的前缀和就可以在 时间内解决这个弱化版的问题与上一题相同，枚举每一个i，暴力更新i的倍数，然后处理前缀和，这样做是O(nlogn)的那么现在有了a的限制怎么搞呢？,BZOJ 3529 数表,我们发
10、现对答案有贡献的i只有F(i)=a的i我们离线处理，将询问按照a排序，i按照F(i)排序每次询问将所有F(i)=a的i按照之前的方式插入 用树状数组维护前缀和即可时间复杂度取模可以利用自然溢出int 最后再对231-1取与即可,BZOJ 2154 Crash的数字表格,题目大意：给定n,m,求(n,m=107)枚举令则有,BZOJ 2154 Crash的数字表格,继续令那么根据莫比乌斯反演可以推出不是很好推，和之前的思路一样，我不当堂推了将两个式子分别进行 的计算 可以得到一个 的算法至此本题已经可以解决。,BZOJ 2693 jzptab,题目大意：同上题 多组数据由于是多组数据 因此上一题的 算法显然超时考虑进一步优化观察后面的，如果我们能对这个函数求出一 个前缀和，那么就可以在 的时间内处理每个询问,BZOJ 2693 jzptab,注意到积性函数的约数和也是积性函数因此后面的那坨东西可以利用线性筛求出来线性筛当 时不满足积性函数的条件，但是由于此时，故多出来的因数的函数值都 是0，增加的只有原先因数的 部分乘了个primej而已这两道题的公式都有些鬼畜，建议写这两道题之前先推推有关公式，权当治疗公式恐惧症了,谢谢大家,
