【开坑】莫比乌斯反演快速入门指南

可能大多数人和我一样第一眼接触莫比乌斯反演的时候自己是懵逼的 ~~数学真珂啪还是学OI好了~~ ~~等等为什么OI考试里面会有纯数学题？~~ 提到莫比乌斯反演的话，就是这类题目标志性的长而复杂的和式运算，以及一个标志性的技法——交换求和号了，这也正是这类题目的难点 不过莫比乌斯反演的套路性还是相当强的，掌握了一般技巧之后做简单的反演题应该不成问题 那么，看完本篇博客，希望诸位可以掌握 关于$\mu,\phi$函数的基本知识 基本的和式运算技巧和交换求和号的知识 莫比乌斯容斥公式 如何列式子和推式子 _本博客仅供介绍莫比乌斯反演入门，关于除数函数的反演不会介绍_ ________________________ ## Part 1 莫比乌斯容斥公式 _事实上这个公式正是莫比乌斯反演的本体_ _不过，由于使用这个公式之后等待你的将会是一系列长到不行的求和号变换，所以仅仅记住这个公式是做不出题来的_ 很简单，就两句话，若数列$f,g$满足如下条件 $$f_{n}=\sum_{d|n}g_{d}$$ 则 $$g_{n}=\sum_{d|n}f_{\frac{n}{d}}\mu(d)$$ 其中函数$\mu$被称为莫比乌斯函数，满足递归式 $$\sum_{d|n}\mu(d)=[n==1]$$ 上面的式子反过来依然成立，也就是是说如果g满足下面的式子可以推出上面的式子 ____________________ #### ~~(可以跳过的)~~证明 先来证明上面的式子可以推出下面的式子 $$g_{n}=\sum_{d|n}f_{\frac{n}{d}}\mu(d)$$ 因为我们已知了 $$f_{n}=\sum_{d|n}g_{d}$$ 所以说我们可以简单粗暴的把上面的式子代入进去 $$g_{n}=\sum_{d|n}\mu(d)\sum_{t|\frac{n}{d}}g_{t}$$ 然后接下来我们发现$d,t$满足这两个限制条件 $$d|n,t|\frac{n}{d}$$ 这两个限制条件等价于这组限制条件 $$d|n,dt|n$$ 也等价于这两组限制条件 $$t|n,dt|n$$ 当然也等价于这两组限制条件 $$t|n,d|\frac{n}{t}$$ 所以我们就可以愉快的将$d,t$的限制条件改变一下，得到 $$g_{n}=\sum_{t|n}g_{t}\sum_{d| \frac{n}{t}}\mu(d)$$ 还记得上面关于$\mu$函数的定义吗?把他代入进去 $$\sum_{d|n}\mu(d)=[n==1]$$ $$g_{n}=\sum_{t|n}g_{t}[\frac{n}{t}==1]$$ 也就是 $$g_{n}=\sum_{t|n}g_{t}[t==n]=g_{n}$$ ~~Quite Easily Done 证明完毕~~ 然后将已知下面的式子推上面的式子的证明过程交(甩)给(锅)读者思考吧~ ______________________________________ ## Part 2 $\mu$和$\phi$以及$\epsilon$ 可能关于$\mu$函数在$part 1$我们已经稍稍介绍了一下 但是莫比乌斯反演当中非常关键的函数还有另外两个$\phi$和$\epsilon$ 先来介绍一下函数$\phi$又名欧拉函数$\phi(x)$ **$\phi(x)=$比x小且与x互质的正整数的数目** 然后介绍另一个看起来没什么卵用的函数$\epsilon(x)$ **$\epsilon(x)=[x==1]$** 最后是我们上一节已经提及的函数$\mu(x)$ 尽管已经有了一个这样的定义(倒不如说我们就是为了这个性质才构造出了函数$\mu$) $$\epsilon(n)=\sum_{d|n}\mu(d)$$ 不过如果我们要求莫比乌斯函数的值的话，更加好的方式是使用下面这个定义 1.如果n的约数中存在平方数，则$\mu(n)=0$ 2.对于其他情况，如果n有奇数个互异的质因子，$\mu(n)=-1$,否则$\mu(n)=1$ 当然你可能会有一个问题，为什么上面的两个定义是等价的？ 下面是~~可以跳过的~~证明 __________________________________ 先来看一下$\mu$的这个定义 $$\epsilon(n)=\sum_{d|n}\mu(d)$$ 我们发现事实上满足这个定义的无穷数列$\mu$只有一个，因为根据这个式子我们事实上可以递推出$\mu$来 所以我们现在只需要证明根据$\mu$函数的第二个定义可以使第一定义成立就行了(否则我们为了证明这两个定义等价还需要证明从第一个定义可以推出第二个定义来) 首先我们将n质因数分解，假设n有p个不同的质因子 那么我们会发现你枚举约数的过程相当于选择一些质因子(可以重复选)把他们乘起来,就得到了一个n的约数 但是如果同一个质数被选了两次，得到的约数就有平方约数了，此时的$\mu$为0 因此真正有符号的$\mu(d)$只有$2^{p}$个 而$\mu$值为+1的数恰好有 $$\sum_{i=0}^{2i+1<=p}C_{p}^{2i+1}$$ 种 $\mu$值为-1的数恰好有 $$\sum_{i=0}^{2i<=p}C_{p}^{2i}$$ 小学数奥告诉我们上面除非p=0否则两个式子相等，所以所有的+1-1都消掉了，最后的结果就是0 但是n==1的时候他没有质因子，所以加起来恰好是1 ______________________________ ## part3 线性筛求$\mu$和$\phi$ 我们已经发现莫比乌斯容斥公式在解决某些问题上可能有不错的效果，比如说一个原来根本没法求的函数我们套个公式容斥下就可以求出他来了 只是还是有个问题是我们怎么求莫比乌斯函数的值 总不能暴力质因数分解然后求吧(不过如果n很大质因数分解是最快的做法) 不过我们发现一个关于$\mu$和$\phi$很有趣的事实 那就是如果$p,q$互质，则$\mu(pq)=\mu(p)\mu(q),\phi(pq)=\phi(p)\phi(q)$ 如果一个函数有类似于$\mu$和$\phi$的这种性质，我们称这个函数为**积性函数**，关于积性函数的芝士此处不再细讲，有兴趣的话可以自行度娘 好了那么积性函数和线性筛有什么关系呢？ 这里我们先粘一份线性筛的代码 ```C /*1*/ int pri[N];int ct;bool book[N]; /*2*/ for(int i=2;i<=N;i++) /*3*/ { /*4*/ if(!book[i])pri[++ct]=i; /*5*/ for(int j=1;j<=ct&&i*pri[j]<=N;j++) /*6*/ { /*7*/ book[i*pri[j]]=true; /*8*/ if(i%pri[j]==0)break; /*9*/ } /*10*/ } ``` 观察一下线性筛的第7行代码 **除非我们执行了第8行代码结束了循环，否则$i,pri[j]$互质** 正确性显然，因为在第8行break掉时质数是i的最小质因子，所以之前的质数必然和i互质 那么假设说我们已知了$\mu(i),\mu(pri[j])$的话，因为$\mu$是个积性函数,我们就可以直接递推出$\mu(i×pri[j])$了 问题来了如果我们执行了第8行代码的话该如何计算$\mu$呢？ 如果第8行代码被执行了，那么意味着$i*pri[j]$有一个约数是$pri[j]^2$ 所以说$\mu$当然是0咯 递推的边界条件是$\mu(1)=1$和如果$p$是质数那么$\mu(p)=-1$ 同理我们发现$phi$也有和$\mu$类似的性质 不巧的是我们的确可以像递推$\mu$一样递推$phi$不过问题来了我们该如何处理执行第8行代码的情况呢？ 有个好消息是如果我们执行了第8行代码的时候$\phi(i×pri[j])=\phi(i)pri[j]$ ______________________________ 这里给出上边的式子的一个小证明(不过不想看证明的直接记结论也没什么关系) 由于$\phi(p^k)=(p-1)p^{k-1}$其中p是一个质数(证明的自己想想，这个实在是不难证明) 由于$phi(pq)=\phi(p)\phi(q)$在p,q互质的时候成立，所以我们假设我们可以将n分解成下面的形式,~~也就是质因数分解~~ $$n=\prod P^{a_{i}}_{i}$$ 那么$\phi(n)$就可以这样求 $$\phi(n)=\prod \phi(p_{i}^{a_{i}})=\prod(p_{i}-1)p^{a_{i-1}}$$ 然后让我们回过头来看当我们执行了线性筛代码中的第8行时的情况，现在我们已经知道$i$和$pri[j]$不互质，希望求出$\phi(i×pri[j])$ 那么我们发现$i×pri[j]$和$i$在质因数分解式的唯一区别就是$pri[j]$的指数加了一个1 又因为$i$和$pri[j]$不互质,所以在i的质因数分解式里面$pri[j]$的指数一定不是0 那么剩下的事情就好说了,既然$pri[j]$的指数不是0那么根据上面那个式子，我们可以直接给$phi(i)$乘一个$pri[j]$就得到了$i×pri[j]$ ________________________ 然后给出线性筛筛$\phi$和$\mu$的代码 这个是筛$\mu$的 ```C int pri[N+10];int book[N+10];int mu[N+10];int ct; mu[1]=1; for(int i=2;i<=n;i++) { if(!book[i])pri[++ct]=i,mu[i]=-1; for(int j=1;j<=ct&&i*pri[j]<=n;j++) { book[i*pri[j]]=true; if(i%pri[j]==0){mu[i*pri[j]]=0;break;}else mu[i*pri[j]]=-mu[i]; } } ``` 这个是筛$\phi$的 ```C int pri[N+10];int book[N+10];int phi[N+10];int ct; phi[1]=1; for(int i=2;i<=n;i++) { if(!book[i])pri[++ct]=i,phi[i]=i-1; for(int j=1;j<=ct&&i*pri[j]<=n;j++) { book[i*pri[j]]=true; if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;} else phi[i*pri[j]]=phi[i]*phi[pri[j]]; } } ``` ______________________________________ ## Part4 狄利克雷卷积和常用的反演结论 _其实这里介绍狄利克雷卷积主要是方便接下来写式子的时候不会写的太长_ 还记得我们一开始讲的莫比乌斯容斥公式吗？ $$f_{n}=\sum_{d|n}g_{d} \Leftrightarrow g_{n}=\sum_{d|n}f_{\frac{n}{d}}\mu(d)$$ 仔细看第二个式子 $$$$