这个文章主要讲一下ACM中1个常用的莫比乌斯反演公式，看到很多博客上面公式是有，但是都没证明，《组合数学》上的证明又没看懂， 就自己想了种证明方法，觉得比《组合数学》的证明简单些，就写一下，希望对初学莫比乌斯反演的同学有帮助。 PS：建议大家看的时候 把公式在纸上写出来！
简单点的说，就是先给出一个函数 F(n) ，然后再由 F(n) 定义一个新函数 G(n) 其中 G(n)=∑F(d) (其中 d 被“包含”于n) 然后 现在我们不知道 F(n) 的值，却知道 G(n) ， 接着我们就可以通过反演由 G(n) 反向得到 F(n)
什么叫 (其中 d 被“包含”于n) ？以及怎么理解反演？ 通过下面的几个例子说明
例1： 我们直接定义 G(n)=∑ni=1F(i) {这里的每个 F(i) ，相对于 G(n) 实际上就是一种包含关系了！！} 然后我们现在已经知道 G(n)=n∗(n+1)/2 ; 接下来 我们要通过 G(n) 反向得到 F(n) 的过程，就是反演 当然，这个问题很简单，很容易都可以看出来 F(n)=n ～～
例2: 我们先令 S,X 都表示集合 比如 S=1,4,6X=2 等 并令 |S| 表示 S 中元素的个数 接着定义 集合上的函数 F(S) //具体怎么定义不用管，我们只需要知道有这么一个关于集合的函数 F 就好了 :) 然后再定义 G(S)=∑F(X) (其中X是S的子集) //这里也是一种包含关系，集合的包含！！ 接着我们不知道 F(S) ，想通过 G(S) 来得到 F(S) 这个问题相对于例1就复杂多了，但实际上我们已经有现成的关于集合包含的莫比乌斯反演公式了 :) F(S)=∑(−1)|S|−|X|G(X) (其中 X 是S的子集) 是不是感觉有点神奇？ 大家可以自己写个程序来验证一下。 下面就是我的验证程序： 我定义 F(S)=|S| ， 然后先 计算出 F(S) ,接着 计算出 G(S) , 然后 比较由 G(S) 反演得到的 F(S) 和 |S| 的大小 下面是 我的程序
#include <iostream> #include <math.h> using namespace std; #define base 10 #define REP(i,n) for(int i=0;i<(n);i++) int F[1<<base],G[1<<base]; // 集合用二进制表示 base表示集合最多10个元素 int Cal(int x){ // 计算 |x| int sum=0; while(x) sum+=(x&1),x/=2; return sum; } int main(){ REP(S,1<<base) F[S]=Cal(S); // 计算出最开始的F(S) REP(S,1<<base){ // 计算G(S) G[S]=0; for(int X=S;X;X=(X-1)&S) G[S]+=F[X]; //用X遍历S集合 } REP(S,1<<base){ // 计算反演的 F(S) F[S]=0; for(int X=S;X;X=(X-1)&S) F[S]+=(int)pow(-1,Cal(S)-Cal(X))*G[X]; } bool flag=1; // 验证一下 REP(S,1<<base) if(F[S]!=Cal(S)) flag=0; if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; }最后得到的结果 当然是 YES 咯！:) 关于这个 反演公式 的证明，先不要着急，看完文章过后，你自己都能摸索着证明了！！ 现在先大概理解反演是个什么就行了！！
例3： 先令 d|n 表示 d 能整除n 比如 2|4 (=.=) 定义关于整数的函数 F(n) 然后定义 G(n)=∑d|n(F(d)) 上面的这种包含关系就更复杂了，只有当 d 是n的因子的时候， F(d) 才会被包含在 G(n) 中。 不过这种 包含关系 在 ACM中遇到的最多，所以我会详细讲一下这种类型的 反演。 相信明白了这个过后，例2的反演也能够自己证明了。 具体的讲解见下一章节 :)
这个一类反演就是例3中的那一类咯= = 我先直接给出结论吧
原式：G(n)=\sum_{d|n}(F(d)) 反演公式：F(n)=\sum(\mu(\frac{n}{d})*G(d))这里\mu是一个函数，他是每一项G(d)的系数，他的定义见下面： （强烈建议关于\mu的定义这一段可以先跳过，先认为他是G的系数就行了，可以跳到下面红字位置）
\mu是一个关于整数的函数\mu[x] = 1 当且仅当 x 能够分解成偶数个不同质数的乘积 （其中1不能被分解，所以1的分解出的质数个数是0，所以\mu[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\leqslant i\leqslant r)有一个数e_{i}大于1 那么 \mu[x] = 0; 不然的话 \mu[x] = (-1)^r 依旧来两个例子（我最喜欢举例子了 = =）
\mu[1]=1;定义中的说明\mu[2]=-1;分解式 2=2;\mu[6]=1; 分解式6=2*3;\mu[9]=0; 9=3^2;出现了e>1\mu[12]=0;12=2^2*3;跳到这里 :)
上面就是关于这类反演公式的定义，不要头晕= =，继续往下看吧 在证明之前，我们先想一下，为什么反演公式会是
F(n)=\sum(\mu(\frac{n}{d})*G(d)) 这样的型式？ 依旧通过例题来找规律 (^ ^) 我们令 n=6; 那么 在计算 F(6)的时候，我们会用到 G(1) G(2) G(3) G(6) 我们考察者4个 G G(1) = F(1) G(2) = F(1)+F(2) G(3) = F(1)+F(3) G(6) = F(1)+F(2)+F(3)+F(6) 观察上面可以发现 每个 G(n)都是由一些 F(d)累加得到的 当我们需要逆向有 G得到F(n)时，只需要将一些 与 F(n) 有关的 G 进行容斥！！！！！最终组合得到F(n)！！！ 比如 F(6) = G(6)-G(2)-G(3)+G(1) 有些神奇！！ 不过这类莫比乌斯反演的实质也就是容斥原理的应用！！那么我们现在知道为什么 这类反演公式会是 这个形式了，而且对其原理也有了更深的理解，现在该想一想公式的细节了。 既然我们知道要得到 F(n)，只需要将与其相关的 G进行容斥就可以，那么剩下的问题就是每个G的系数！！！ 我们以 求解 F(6)为例子来说明 ，并定义一个系数函数 H(d,n). 其中 H(d,n)表示 求解F(n)时，G(d)的系数 （其中d|n） 所以可以得到这个式子
F(6) = H(6,6)*G(6)+H(2,6)*G(2)+H(3,6)*G(3)+H(1,6)*G(1) 我们用 a,b,c,d分别替代 四个 H(6,6),H(2,6),H(3,6),H(1,6) 并且把对应的 G用F表示出来，得到 F(6)=a*(F(6)+F(3)+F(2)+F(1))+b*(F(2)+F(1))+c*(F(3)+F(1))+d*F(1) 再变形一下，又有 F(6)*(a-1)+F(3)*(a+c)+F(2)*(a+b)+F(1)*(a+b+c+d)=0 把 F(6),F(3),F(2),F(1)当作不同的元，则得到了下面的方程组！！！ a-1=0 a+c=0 a+b=0 a+b+c+d=0 由此发现，四个未知数，四个方程，只需要解出方程，就能知道对于G的系数。 再深入的想一下，对于每个 F(n),假设他的因子数为 m，则通过这种方式，总能设出m个未知数， m个方程，这样总能找到解，而这也为莫比乌斯反演的可能性作出了解释！！现在我们要证明一个结论，即使H(a,b)=H(1,\frac{b}{a})！！这个结论很重要，具体分析见下 :)
我们以求解 F(8)为例子，与F(8)相关的H有H(8,8),H(4,8),H(2,8),H(1,8)
F(8)=H(8,8)*G(8)+H(4,8)*G(4)+H(2,8)*G(2)+H(1,8)*G(1) 首先看 H(8,8),其值可以直接确定，因为把 F(8)当作元的话，左边一个 F(8),而在右边 F(8)只在 G(8)中出现，所以 H(8,8)=1同理 对于 F(n)，其G(n)的系数H(n,n)=1，所以H(8,8)=H(1,1)
再来看H(4,8)： 首先想，F(4)在哪些地方出现 发现在G(8)和G(4)出现，因为左边不含F(4)，而前面G(8)的系数又已经确定 所以这里H(4,8)*G(4)的作用就是为了抵消前面G(8)的代换中，出现的F(4) 所以 H(4,8)=-H(8,8)=-H(2,2)=H(1,2) //H(1,2)=-H(1,1)请大家自己验证一下
同理对于H(2,8)： 他是为了抵消前面在G(8)和G(4)中出现的F(2) 所以H(2,8)相当于受到H(4,4)和H(2,4)的影响(假设这个结论对n=4也成立，H(2,4)=H(1,2)) 所以H(2,8)==H(1,4)
找到规律过后，总结一下：
假设n的因子有 d_{1},d_{2},d_{3},...,d_{m} 其中 d_{1}>d_{2}>d_{3}>...>d_{m}我们依次确定H(d_{i},n)的值： 当我们在确定H(d_{i},n)的值时，前面的值已经确定 即H(d_{j},n)(j<i)的值已经确定 H(d_{i},n)会受到前面一些H(d_{j},n)的影响，当且仅当 d_{j}>d_{i}且 d_{i}|d_{j} 。
假设 H(a,b)=H(1,\frac{b}{a})对前面的 H(d_{j},n) 和所有的H(k,m)其中m<n 已经成立(首先对于H(n,n)已经成立) 那么有H(d_{j},n)=H(1,\frac{n}{d_{j}})=H(\frac{d_{j}}{d_{i}},\frac{n}{d_{i}}) 这样就把前面对H(d_{i},n)造成影响的H<script type="math/tex">H</script>由 H(d_{j},n)转为了H(\frac{d_{j}}{d_{i}},\frac{n}{d_{i}}) 所以H(d_{i},n) = H(1,\frac{n}{d_{i}})
既然 H(a,b) 都可以 写成 H(1,\frac{b}{a}) ， 于是我们把H的第一个元素略去，简写为H(x) 说到这里，就可以把H和\mu联系起来了，其实 \mu(x) = H(x) = H(1,x) 再来，我们就可以给\mu(x)赋予一个更具体的意义， \mu(x)表示在计算 F(x)时，G(1)的系数！！(因为\mu(x)=H(1,x))
接下来，我们来尝试一下，如何用上面那个\mu(x)的新意义，来计算\mu(x)的值！！ 首先需要明确2点！ 一是G(x)中,一定包含一个F(1)，因为 1|x 二是，F(1)=G(1)
(0).如果 x=1 因为 F(1)=G(1) 所以 \mu[1]=1;
(1).假设 x 是一个 质数 F(x) = \mu(1)*G(x)+\mu(x)*G(1) 带入\mu(1) = 1, 因为G(x)中含有一个F(1),而左边不含F(1)，所以我们需要利用G(1)来消去F(1) 所以得到 \mu(x)=-1
(2).假设 x 可以写成2个不同质数的乘积 x=p*q 那么 F(x)=\mu(1)*G(pq)+\mu(q)*G(p)+\mu(p)*G(q)+\mu(x)*G(1) 这里 \mu(1)，\mu(p)，\mu(q) 就是前面2种情况 带入系数，因为左边没有 F(1)，所以为了抵消右边的F(1)，我们需要令 \mu(x)=1;
(3).假设 x 可以写成3个不同质数的乘积 x=p*p1*p2 我们令 z = p1*p2 F(x) = \mu(1)*G(pz)+\mu(z)*G(p)+\mu(p)*G(z)+\mu(x)*G(1); 其中 \mu(1),\mu(p),\mu(z) 分别为前面几种情况，带入过后 ，为抵消F(1) 得到 \mu(x)=-1 由此可以相同的方式向下递推，得到第一条结论
如果 x = p_{1}*p_{2}...*p_{r} , 其中p_{i}是互异的质数，那么 \mu[x] = (-1)^r(4).假设 x 可以写成一个质数的平方 x=p^2 F(x) = \mu(1)*G(x)+\mu(p)*G(p)+\mu(x)*G(1) 带入系数 得到 \mu(x)=0;
(5).假设 x 可以写成一个质数的三次方 x=p^3 F(x) = \mu(1)*G(x)+\mu(p)*G(p^2)+\mu(p^2)*G(p)+\mu(x)*G(1) 带入系数后 \mu(x)=0; 由此可用相同方式向下递推，得到第二条结论
如果 x = p^e (e>1),那么\mu[x] = 0(6).假设 x 可写成 x = p^e*q 其中p,q为不同质数，e>1 F(x) = \mu(1)*G(x)+\mu(q)*G(p^e)+\mu(p^e)*G(q)+\mu(x)*G(1) 带入系数后 \mu(x) = 0; 由此可继续向下递推，得到第二条结论的加强版！！
如果 x = p^e*z 其中p为质数, z为任意数,e>1 那么 \mu[x] = 0由此，我们得到了 \mu[x] 的计算方法！！即是\mu定义中给出的那样！！（没看定义的同学此时再跳回去看吧）
得到了公式，也知道了他是怎么来的，现在就用一个应用来加深理解吧 :) 首先我们要给出 第二部分 中那个公式的另外一种形式 = = 我们把它称为形式二吧～
原式: G(n)=∑n|d(F(d)) 反演公式: F(n)=∑(μ(dn)∗G(d)) 这里 μ[x] 的计算方式和上面的相同！！ 注意上面的 n|d 和 d/n 和上面是相反的 证明方法和上面差不多，大致说一下 还是先设置一个系数函数 H(d,n) 表示求解 F(n) 时 G(d) 出现的次数 接着 用与上面类似的方法变化 H(d,n) 为 H(dn,1) —> H(x,1) 则联系 μ(x)=H(x,1) 表示 在计算 F(1) 时， G(x) 的系数 以 x 为质数为例子，由于 G(1)=F(1) F(2) ... F(N) 故 F(1)=G(1)+μ(2)G(2)+...+μ(x)G(x)+...+μ(N)G(N) 因为 x 为质数 所以 F(x)这一项 只在 G(1) 里面出现了一次，而其他地方只会在 G(x) 出现 所以我们需要让 μ(x)=−1 来抵消 F(x) 剩下的步骤就和上面差不多了，分类讨论一下，就可以求出这种情况下的 μ 的计算方式，和上面相同！！接下来就真正的开始演示怎么用 莫比乌斯反演 简化计算了 ！！ 看下面这个问题！ 给出 a,b ,其中 1⩽a,b⩽106 求满足条件的 x,y 的对数，使得 1⩽x⩽a,1⩽y⩽b ,且 gcd(x,y)=1 。 其中 (2,3)(3,2) 算两对！ 直接暴力显然复杂度太大，我们用莫比乌斯反演来解决。 令 N=max(a,b) 然后定义 F(n) 表示满足条件的 gcd(x,y)=n 的 (x,y) 对数 在定义 G(n) 表示满足 n|gcd(x,y) 的 (x,y) 对数 即 gcd(x,y)≡0(modn) 的 x,y 对数 那么根据定义，有 G(n)=∑n|d(F(d)) 于是我们需要求的就是 F(1) 怎么解决？ 首先根据 G(n) 的定义，可以很容易发现
G(n)=(⌊an⌋)∗(⌊bn⌋) （提示：把 n 当成最小的元） 然后 我们只直接计算 F(1) 即可 带入 G(n) 的公式 有 F(1)=∑ni=1(μ[i]∗(⌊ai⌋)∗(⌊bi⌋)) 至于 μ[] 的值，可以提前用筛法在 O(n) 的时间内处理出来，这样总的时间复杂度就是 O(n) ，问题得到解决！！下面附上我自己求 μ[] 的代码 （效率并不是严格上的 O(n) ，不过一般情况下已经足够）
#include <iostream> #include <cstring> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,j,k) for(int i=j;i<=(k);i++) #define maxn 1000009 int u[maxn]; bool vis[maxn]; void Work(){ // 计算U[] memset(vis,0,sizeof(vis)); memset(u,0,sizeof(u)); for(int i=2;i<maxn;i++) if(!vis[i]) for(int j=i;j<maxn;j+=i){ if(u[j]==-1) continue; if((j/i)%i==0) u[j]=-1; else u[j] ++; vis[j]=1; } FOR(i,1,maxn-1) if(u[i]==-1) u[i]=0; else if(u[i]%2) u[i]=-1; else u[i]=1; } int main(){ Work(); }在ACM中，可以利用 莫比乌斯反演 来求解很多关于 Gcd 的问题 推荐几道基础题： SPOJ 7001 , ZOJ 3435, HDU 1695. 想做更多的题的话，自己去HUST OJ搜索吧 :)
最后再说一下上面的证明方法都是个人YY的，感觉比《组合数学》上的证明简单些（数学太渣orz…那个证明我是没看太懂），写下来 给初学莫比乌斯反演的童鞋当个资料（= =）。关于上面的证明我暂时没发现什么错误，如果发现错误，请在回复里面指出！另外 形式二的证明应该可以由形式一直接得到，不过我没想出什么好办法，知道的神牛也请在评论中说一下！
(￣.￣) 完～～
