36莫比乌斯反演

莫比乌斯反演——吉大附中实验学校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)|()()dnFnfd于是我们可以通过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)-F(2)+F(1)•f(7)=F(7)-F(1)•f(8)=F(8)-F(4)•在推导的过程中我们是否发现了一些规律？莫比乌斯反演•公式：•其中为莫比乌斯函数，定义如下：•(1)若则•(2)若，为互异素数，那么•(3)其它情况下||()()()()()dndnnFnfdfndFd()d1d()1d12...kdpppip()(1)kd()0d莫比乌斯函数的性质•(1)对于任意正整数n有：•证明：•①当时显然•②当时，将分解可以得到•在的所有因子中，值不为零的只有所有质因子次数都为1的因子，其中质因数个数为个的因子有个•那么显然有：|1(1)()0(1)dnndn1n1nn1212...kaaaknpppn012|0()...(1)(1)kkkiikkkkkdnidCCCCCrrkC莫比乌斯函数的性质•只需证明即可•二项式定理：•令，代入即可得证。0(1)0()niiniCnN0()nniininixyCxy1,1xy莫比乌斯函数的性质•(2)对于任意正整数n有：•其实没什么用，结论挺好玩的可以记一下•只需要令，代入莫比乌斯反演的公式即可•至于为什么就留给大家做思考题了|()()dndndn(),()()Fnnfnn|()dnnd莫比乌斯函数的性质•(3)积性函数•数论上积性函数的定义：•积性函数的性质：•①•②积性函数的前缀和也是积性函数()(,)1()()()()()()()()fnNxyfxyfxfyfnxyfxyfxfyfn设为一个定义在集合上的函数，如果对于任意有，则称为一个积性函数；若对于任意和均有，则称为一个完全积性函数(1)1f莫比乌斯函数的性质•由于莫比乌斯函数是积性函数，因此我们可以通过线性筛来求出莫比乌斯函数的值•代码：•mu[1]=1;•for(i=2;i=n;i++)•{•if(!not_prime[i])•{•prime[++tot]=i;•mu[i]=-1;•}•for(j=1;prime[j]*i=n;j++)•{•not_prime[prime[j]*i]=1;•if(i%prime[j]==0)•{•mu[prime[j]*i]=0;•break;•}•mu[prime[j]*i]=-mu[i];•}•}BZOJ2440完全平方数•题目大意：求第k个无平方因子数•无平方因子数(Square-FreeNumber)，即分解之后所有质因数的次数都为1的数•首先二分答案问题转化为求[1,x]之间有多少个无平方因子数•根据容斥原理可知对于sqrt(x)以内所有的质数有•x以内的无平方因子数•=0个质数乘积的平方的倍数的数的数量(1的倍数)•-每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...)•+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,...)-...BZOJ2440完全平方数•容易发现每个乘积a前面的符号恰好是(例如故9对答案的贡献为负；，故36对答案的贡献为正)•x以内i^2的倍数有个故有•这题和莫比乌斯反演没关系，算是莫比乌斯函数的一个应用吧。。。()a(3)1,(6)12xi21()()xixQxii现在我们来证明莫比乌斯反演定理•证明：•这里利用到了这条性质•形式二：•证明同理一般要用到的都是这种形式||()()()()()dndnnFnfdfndFd|||||()()()()()()()()nndndnknkddknfndFdfkfkdfnd|1(1)()0(1)dnndn||()()()()()ndnddFnfdfnFdn有了这个定理，我们能干什么？•对于一些函数f(n)，如果我们很难直接求出它的值，而容易求出倍数和或约数和F(n)，那么我们可以通过莫比乌斯反演来求得f(n)的值•例：f(n)表示某一范围内(x,y)=n的数对的数量，F(n)表示某一范围内n|(x,y)的数对的数量•那么直接求f(n)并不是很好求，而F(n)求起来相对无脑一些，我们可以通过对F(n)进行莫比乌斯反演来求得f(n)•下面用几道例题来为大家讲解一下莫比乌斯反演的好处BZOJ2301Problemb•n次询问，每次询问有多少个数对(x,y)满足a=x=b,c=y=d且gcd(x,y)=k•N=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)的算法，但是这显然不能胜任此题的数据范围•这时候我们就可以考虑莫比乌斯反演了BZOJ2301Problemb•由于之前的结论，我们可以令f(i)为1=x=n,1=y=m且gcd(x,y)=i的数对(x,y)的个数，F(i)为1=x=n,1=y=m且i|gcd(x,y)的数对(x,y)的个数•那么显然有•反演后可得•枚举原题中k的每一个倍数，我们就可以O(n)时间处理每个询问了•但是O(n)还是不能胜任本题的数据范围•考虑进一步优化||()()()()ididddnmfiFdiidd()nmFiiiBZOJ2301Problemb•观察式子，发现最多有个取值•那么就至多有个取值•枚举这个取值，对莫比乌斯函数维护一个前缀和，就可以在时间内出解•总时间复杂度•枚举除法的取值这种方法在莫比乌斯反演的应用当中非常常用，且代码并不难写•不难写？怎么写？nd2nnmdd2()nm2()nm()n()nnBZOJ2301Problemb•if(nm)swap(n,m);•for(i=1;i=n;i=last+1)•{•last=min(n/(n/i),m/(m/i));•re+=(n/i)*(m/i)*(sum[last]-sum[i-1]);•}•returnre;•超级好写不是么？BZOJ2820YGY的GCD•题目大意：求有多少数对(x,y)(1=x=n,1=y=m)满足gcd(x,y)为质数•n,m=1000W数据组数=1W•首先我们枚举每一个质数那么答案就是•直接做显然TLE考虑优化•令，那么有min(,)min(,)1()nmnmpdnmansdpdpdpdTmin(,)1|()nmTpTnmTansTTpBZOJ2820YGY的GCD•如果能求出的前缀和，这个问题就能在时间内出解。•只需要暴力枚举每一个质数，去更新这个质数的倍数即可。•由这个结论易知每个质数更新时是均摊的，而质数个数恰好为•故暴力枚举+维护前缀和的时间复杂度即为。|()pTTp()n11limlnnninri(log)n(/log)nn()nBZOJ3529数表•题目大意：令F(i)为i的约数和，q次给定n,m,a,求•n,m=10^5,q=2W,a=10^9•a的限制十分讨厌我们首先假设没有这个限制•令g(i)为1=x=n,1=y=m,gcd(x,y)=i的数对(x,y)的个数•那么显然有3111(gcd(,))(gcd(,))mod2injmFijaFij|()()iddnmgiiddBZOJ3529数表•F(i)利用线性筛可以在O(n)时间内处理出来那么就有•治好了我多年的公式恐惧症~~•现在我们只要有的前缀和就可以在时间内解决这个弱化版的问题•与上一题相同，枚举每一个i，暴力更新i的倍数，然后处理前缀和，这样做是O(nlogn)的•那么现在有了a的限制怎么搞呢？min(,)min(,)min(,)11|1|()()()()()()nmnmnmiiiddiddnmnmdansFigiFiFiiddddi|()()iddFii()nBZOJ3529数表•我们发现对答案有贡献的i只有F(i)=a的i•我们离线处理，将询问按照a排序，i按照F(i)排序•每次询问将所有F(i)=a的i按照之前的方式插入用树状数组维护前缀和即可•时间复杂度•取模可以利用自然溢出int最后再对2^31-1取与即可2(loglog)nnqnnBZOJ2154Crash的数字表格•题目大意：给定n,m,求(n,m=10^7)•枚举•令•则有11(,)nmijlcmij1111(,)gcd(,)nmnmijijijanslcmijijgcd(,)dij11gcd(,)1(,)ixjyijFxyij2min(,)min(,)11(,)(,)nmnmddnmdFnmddansdFdddBZOJ2154Crash的数字表格•继续令•那么根据莫比乌斯反演可以推出•不是很好推，和之前的思路一样，我不当堂推了•将两个式子分别进行的计算可以得到一个的算法•至此本题已经可以解决。11(1)(1)(,)22yxijxxyySumxyijmin(,)21(,)()(,)xyixyFxyiiSumii()n()()nnnBZOJ2693jzptab•题目大意：同上题多组数据•由于是多组数据因此上一题的算法显然超时•考虑进一步优化•观察后面的，如果我们能对这个函数求出一个前缀和，那么就可以在的时间内处理每个询问()nmin(,)min(,)211min(,)21|()(,)(,)()nmnmdinmDiDnmansdiiSumdidinmDSumiiDDi2|()iDDiii()nBZOJ2693jzptab•注意到积性函数的约数和也是积性函数•因此后面的那坨东西可以利用线性筛求出来•线性筛当时不满足积性函数的条件，但是由于此时，故多出来的因数的函数值都是0，增加的只有原先因数的部分乘了个prime[j]而已•这两道题的公式都有些鬼畜，建议写这两道题之前先推推有关公式，权当治疗公式恐惧症了mod0jiprime()0jprimeiDi