> ## Content Index > Fetch the complete content index at: https://blog.hacking.pub/llms.txt > Use this file to discover other available public pages before exploring further. # 莫比乌斯反演 - URL: https://blog.hacking.pub/2016/11/15/mo-bi-wu-si-fan-yan-2/ - Published: 2016-11-15T17:39:34.000Z - Updated: 2017-05-04T09:21:25.000Z - Author: chainhelen - Tags: acm, 算法, 数论, mathjax, 莫比乌斯反演 #### 定义 定理:\\(F(n)\\)与\\(f(n)\\)是非负整数集合上的两个函数，并且满足\\(F(n)=\\sum\_{d|n}^{} f(d)\\)公式，那么就有$$f(n)=\\sum\_{d|n}^{} \\mu(d)F({n \\over d})$$ 上述函数\\(\\mu(d)\\),就是莫比乌斯函数 定义如下: 1. 若 \\(d = 1\\)，则 \\(\\mu(d) = 1\\) 2. 若 \\(d = p\_1p\_2 \\cdots p\_k\\), 其中 \\(p\_i\\)互质，那么 \\(\\mu(d)=(-1)^{k}\\) 3. 其他情况下 \\(\\mu(d)=0\\) #### 性质 1. 对任意正整数\\(n\\)有: $$\\sum\_{d|n} \\mu(d) = \\begin{cases} 1 & (n=1) \\\\ 0 & (n>1) \\\\ \\end{cases}$$ 证明： (1)当\\(n=1\\)时显然 (2)当\\(n\\neq1\\)时，\\(n\\)分解可以得到\\(n=p\_{1}{a\_1}p\_{2}{a\_2} \\cdots p\_{k}^{a\_k}\\)，故\\(d\\)的取值就是 \\(d=p\_1{b\_1}p\_2{b\_2} \\cdots p\_k^{b\_k} \\quad 0 \\le b\_i \\le a\_i, i=1,2 \\ldots k\\)，可以得到 $$\\mu(d)=\\mu(p\_1{b\_1}p\_2{b\_2} \\cdots p\_k^{b\_k}) \\quad 其中 0 \\le b\_i \\le a\_i, i=1,2 \\ldots k$$ 根据定义2、3看，\\(b\_i\\)一定是0或1，\\(\\mu(d)\\)才不等于０，现在我们对不为零的项求和. d包含r个质因子的项数为\\({k \\choose r}\\)，那么根据性质２可以得到 $$ \\begin{align} \\mu(d) &={k \\choose 0} - {k \\choose 1} + {k \\choose 2} + \\cdots +(-1)^k {k \\choose k} \\\\ &= \\sum\_{i=0}{k}(-1)i{k \\choose i} \\\\ &= \\sum\_{i=0}{k}(-1)i(1)^{k-i}{k \\choose i} \\\\ &= (-1 + 1)^k \\quad(二项式定理)\\\\ &= 0 \\\\ \\end{align} $$ 即证 2. 对于任意正整数\\(n\\)有 $$\\sum\_{d|n}\\frac{\\mu(d)}{d}={\\phi(n) \\over n}$$ 证明过程略，只要将\\(F(n)=n，f(n)=\\phi(n)\\)带入，交叉相乘即可 #### 证明 一开始，没太懂证明 $$\\sum\_{d|n}^{} \\mu(d)F({n \\over d})=\\sum\_{d|n}\\mu(d)\\sum\_{d'|{n \\over d}}f({d'})=\\sum\_{d'|n}f(d')\\sum\_{d|{n \\over d'}}\\mu(d)=f(n)$$ 后来我举了了个例子，才明白写成下面方式会更懂点 $$\\sum\_{d|n}^{} (\\mu(d)\*F({n \\over d}))=\\sum\_{d|n}(\\mu(d)\*\\sum\_{d'|{n \\over d}}f({d'})) = \\sum\_{d'|n}(f(d')\*\\sum\_{d|{n \\over d'}}\\mu(d))=f(n)$$ 1. 先看第二个等号是怎么过去的，假如求\\(f(12)\\)，公式如下： $$f(12)=\\sum\_{d|12}^{} (\\mu(d)\*F({12 \\over d}))$$ 按照d的值可以将各项式拆成： $$\\begin{align} F(1) &= \\mu(1)\*f(1) +\\mu(1)\*f(2)+\\mu(1)\*f(4)+\\mu(1)\*f(6)+\\mu(1)\*f(12) \\\\ F(2) &= \\mu(2)\*f(1) +\\mu(2)\*f(2)+\\mu(2)\*f(3)+\\mu(2)\*f(6) \\\\ F(3) &= \\mu(3)\*f(1) +\\mu(3)\*f(2)+\\mu(3)\*f(4) \\\\ F(4) &= \\mu(4)\*f(1) +\\mu(4)\*f(3) \\\\ F(6) &= \\mu(6)\*f(1) +\\mu(6)\*f(2) \\\\ F(12) &= \\mu(12)\*f(1)\\\\ \\end{align}$$ 注意仔细看，例如能与f(2)相乘的有，\\(\\mu(1)，\\mu(2)，\\mu(3)，\\mu(6)\\). 整个多项式中能与\\(f(x)\\)相乘的\\(\\mu(y)\\). 可以观察到y值的范围，y 是取尽了\\(x\*y\\le n\\)并且\\(y|n\\). 所以对于含有\\(f(d)\\)的项就是 $$\\begin{align} f(x)\*\\sum\_{y|{n \\over x}}\\mu({n \\over x}) \\end{align}$$ 而x取所有满足x|d的值，故上面第二个等式化简为， $$\\sum\_{d|n}(\\mu(d)\*\\sum\_{d'|{n \\over d}}f({d'})) = \\sum\_{d'|n}(f(d')\*\\sum\_{d|{n \\over d'}}\\mu(d))$$ 2. 再来看看等三个等号怎么过去的，前面已经有结论:\\(\\sum\_{k|n} \\mu(k) = \\begin{cases} 1 & (n=1) \\\\ 0 & (n>1) \\\\ \\end{cases}\\)，所以当且仅当\\(n|d'\\)等于１，即d'=n的时候\\(\\sum\_{d|{n \\over d'}}\\mu(d)\\)是１，其他时候都等于０. 所以得到: $$ \\sum\_{d'|n}(f(d')\*\\sum\_{d|{n \\over d'}}\\mu(d))=f(n) $$ #### 入门实战 [hdu1695](http://acm.hdu.edu.cn/showproblem.php?pid=1695&ref=blog.hacking.pub) 题目大致意思是变量\\(x\\)与\\(y\\)满足\\(a \\le x \\le b\\) ，\\(c \\le y \\le d\\)，（其中a = 1，c = 1，b、d未知），求有多少对\\((x，y)\\) 使得\\(GCD(x，y) = k\\) 解法: 1. 很容易想到题目可以**转化**为满足，\\(1 \\le x \\le {b \\over k} \\quad 1 \\le y \\le {d \\over k}\\)，（b、d未知），使得\\(GCD(x，y) = 1\\)的\\((x，y)\\) 对数 设\\(f(i)\\)代表满足\\(GCD(x，y) = i\\)的\\((x，y)\\)对数，我们需要求的是\\(f(1)\\) 则\\(F(i)\\)代表满足\\(GCD(x，y) = i\\)正整数倍数的\\((x，y)\\)对数，很容易知道\\(F(i)=\[{b \\over k} / i\] \* \[{d \\over k} / i\] \\) 记\\(f(1)=M\\) 2. 当然按照题意需要**去掉重复**的，比如\\((n\_1，n\_2)\\)与\\((n\_2，n\_1)\\) 仔细观察，重复的的\\(x，y\\)其实只在\\( 1 \\le x \\le min({b \\over k}, {d \\over k}) \\)与\\( 1 \\le y \\le min({b \\over k}, {d \\over k}) \\)中出现，那么可以利用\\(F^{'}(i)=\[min({b \\over k}, {d \\over k}) / i\] \* \[min({b \\over k}, {d \\over k}) / i\]\\)，同理可得对数结果 记\\(f{'}(1)=M{'}\\) 对于\\(f^{'}(１)\\)来看，如果\\(x \\gt y\\)的情况有\\(n\\)个，那么\\(x \\lt y\\)的也有\\(n\\)个，另外还有\\(x == y\\)，有且仅有一个那就是\\((1, 1)\\) ，所以\\(M^{'} = 2 \* n + 1\\)，只要结果M中去除掉\\(\[M^{'} / 2\] = \[(2 \* n + 1) / 2\] = n\\) 3. \\(\\mu(i)\\)是**积性函数**，本来按照定义就可以直接求出值，类似于筛法＋打表，提前记录出素数. 但是其实可以利用\\(\\sum\_{d|n}\\mu(d) = 0 \\quad (当n != 1)\\) . 按顺序求出\\(\\mu(i)\\)，所以当求到\\(\\mu(n)\\)的时候， 只要将\\(0 - \\sum\_{d|n && d \\neq n}\\mu(d)\\)即可，所以在求出\\(\\mu(n)\\)之前，\\(\\mu(n)\\)可以用来存储\\(\\sum\_{d|n && d \\neq n}\\mu(d)\\)，并不断更新该值. 4. 这道题**有道坑**，就是\\(k\\)可以为0 ```c #include #include #include using namespace std; const int N = 1e5+5; int mu[N]; void getMu(){ memset(mu, 0, sizeof(mu)); for(int i = 1;i < N;i++) { int sum = i == 1 ? 1 : 0; mu[i] = sum - mu[i]; for(int j = 2;j * i < N;j++) { mu[j * i] += mu[i]; } } } int m, t; int a, b ,c , d, k; int main() { getMu(); scanf("%d", &t); for(int ii = 1;ii <= t;ii++) { scanf("%d %d %d %d %d", &a, &b, &c, &d, &k); long long ans1 = 0; long long ans2 = 0 ; if(0 == k) { printf("Case %d: %lld\n", ii, 0LL); continue; } b /= k; d /= k; if(b > d) { swap(b, d); } for(int i = 1;i <= b;i++) { ans1 += (long long)mu[i] * (b / i) * (d / i); } for(int i = 1;i <= b;i++) { ans2 += (long long)mu[i] * (b / i) * (b / i); } printf("Case %d: %lld\n", ii, ans1 - ans2 / 2); } return 0; } ``` **未经同意，禁止转载** [本文地址 http://blog.hacking.pub/2016/11/15/mo-bi-wu-si-fan-yan-2/](https://blog.hacking.pub/2016/11/15/mo-bi-wu-si-fan-yan-2/) #### 参考 - [维基百科 默比乌斯反演公式](https://zh.wikipedia.org/wiki/%E9%BB%98%E6%AF%94%E4%B9%8C%E6%96%AF%E5%8F%8D%E6%BC%94%E5%85%AC%E5%BC%8F?ref=blog.hacking.pub) - [csdn blog 莫比乌斯反演](http://blog.csdn.net/acdreamers/article/details/8542292?ref=blog.hacking.pub) - [MathJax的一些坑](https://www.douban.com/note/534786000/?type=rec&ref=blog.hacking.pub) - [Mathjax与LaTex公式简介](http://mlworks.cn/posts/introduction-to-mathjax-and-latex-expression/?ref=blog.hacking.pub) - [莫比乌斯反演 ppt](http://wenku.baidu.com/link?url=zJW6jFebE-1MP2JtNHVQ33V4eR6XZRhtAS16vni5Peo4sq7W2t9Z2QoHr7cnj5y1eV-VY2z39SarH6%5FxiBiknEUuAGpbRowBE2LItxIbshq&ref=blog.hacking.pub) #### 吐槽 markdown + mathjax 因为转义把\\(写成\\\\(之外，还有\\sum\_也要写成\\sum\\\_，因为\_会被markdown干掉，问题是如果一行之中只有一个\\sum\_的时候，使用\\sum\_没有问题的，出现两个就不行了