Mobius反演总结

#**莫比乌斯反演** Tags：数论 ##更好阅读体验：https://www.zybuluo.com/xzyxzy/note/1015992 --- ##**引用** YYB：http://www.cnblogs.com/cjyyb/p/7953803.html YL：http://www.cnblogs.com/cjoieryl/p/8250019.html ZSY：http://www.cnblogs.com/zhoushuyu/p/8186224.html ##**一、基本内容** 《组合数学》P142写了详细内容，这里简单提一下： ##**Step1 Mobius函数** ####**定义：** $$\mu(d)=\begin{cases} 1\quad \quad \quad d=1\\ {(-1)}^r \quad d=p1p2p3...pr\\ 0\quad \quad \quad 其他\end{cases}$$ ####**定理：** 对于任意正整数n，恒有$$\sum_{d|n}\mu(d)=\begin{cases} 1 \quad n=1 \\ 0 \quad n>1 \end{cases}$$ ####**证明：** $n$为$1$的时候很好证明，$n>1$的如下 首先$n$转化为$n'$，$n={p1}^{a1}{p2}^{a2}...{pk}^{ak}$,$n'=p1p2...pk$。 那么对于$d$有$n|d$那么$\mu(d)$无贡献，推出$\mu(n)=\mu(n')$ 在$k$个质数中选$0$个（偶数个系数是$1$，由定义得）$+C(k,0)$，选$1$个（奇数个系数是$-1$）$-C(k,1)$，最后的式子就是（组合数公式） $$C(k,0)-C(k,1)+C(k,2)-...\pm C(k,k)=0$$ ##**Step2 Mobius反演** ####**形式A**： $$g(x)=\sum_{d|x}f(d)$$ $$f(x)=\sum_{d|x}\mu(\frac{x}{d})g(d)$$ ####**形式B**： $$g(x)=\sum_{x|d}^{n}f(d)$$ $$f(x)=\sum_{x|d}^{n}\mu(\frac{d}{x})g(d)$$ 这里给出形式$A$的证明 ####**证明：** $$f(x)=\sum_{d|x}\mu(\frac{x}{d})\sum_{d'|d}f(d')$$ 对于每一个$f(d')$，如果说它要被计算到，那么一定存在一个$d$使得$d|x$且$d'|d$ 那么就是$\frac{x}{d'}|\frac{x}{d}$，被计算的次数是$\mu(\frac{x}{d})$ $$f(x)=\sum_{d'|x}f(d')\sum_{\frac{x}{d'}|\frac{x}{d}}\mu(\frac{x}{d})$$ 然后由上面的定理得出当且仅当$\frac{x}{d}$为$1$时$\mu(\frac{x}{d})$不为$0$，为$1$，进而 $$x=d,f(x)=\sum_{d'|1}f(d')=f(x)$$ 形式$B$同理可证，核心思想是**把贡献提出来** ###**Step 3 举个例子** 求:$$\sum_{i=1}^{N}\sum_{j=1}^{M}[gcd(i,j)==1]$$ ####**Way 1** 令$$f(x)=\sum_{i=1}^{N}\sum_{j=1}^{M}[gcd(i,j)==x]$$ $$g(x)=\sum_{x|d}^{min(N,M)}f(d)$$ 那么（中括号内表示成立为$1$否则为$0$）$$g(x)=\sum_{x|d}^{min(N,M)}\sum_{i=1}^{N}\sum_{j=1}^{M}[gcd(i,j)==d]$$$$=\sum_{i=1}^{N}\sum_{j=1}^{M}[x|gcd(i,j)]=\lfloor\frac{N}{x}\rfloor\lfloor\frac{M}{x}\rfloor$$ 进而$$f(x)=\sum_{x|d}^{min(N,M)}\mu({\frac{d}{x}})g(d)$$$$f(1)=\sum_{i=1}^{min(N,M)}\mu(i)\lfloor\frac{N}{i}\rfloor\lfloor\frac{M}{i}\rfloor$$ 加上数论分块可以$O(\sqrt{N})$完成（[数论分块例题][1]） ####**Way 2** 由上面的莫比乌斯函数的定理可以知道$$[gcd(i,j)==1]=\sum_{d|gcd(i,j)}\mu(d)=\sum_{d|i,d|j}\mu(d)$$ 所以说$$Ans=\sum_{i=1}^{N}\sum_{j=1}^{M}\sum_{d|i,d|j}\mu(d)$$ **提贡献**：把$d$提到前面来$$Ans=\sum_{d=1}^{min(N,M)}\mu(d)\sum_{d|i}^{N}\sum_{d|j}^{M}1$$即$$Ans=\sum_{d=1}^{min(N,M)}\mu(d)\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor$$ ##**二、题目** ###**1、练基础** 【HDU】GCD https://vjudge.net/problem/HDU-1695 【Luogu】[POI2007]ZAP-Queries [https://www.luogu.org/show/3455][2] 【Luogu】[HAOI2011]Problem b [https://www.luogu.org/show/P2522][3] 【Luogu】[SDOI2008]仪仗队 https://www.luogu.org/problemnew/show/P2158 【SPOJ】Visible Lattice Points https://vjudge.net/problem/SPOJ-VLATTICE 【ZOJ】Ideal Puzzle Bobble https://vjudge.net/problem/ZOJ-3435 【Luogu】[NOI2010]能量采集 https://www.luogu.org/problemnew/show/P1447 【CJOJ】gcd之和 https://oj.changjun.com.cn/problem/detail/pid/2512 【UVa】GCD-Extreme(II) https://vjudge.net/problem/UVA-11426 【Luogu】[国家集训队]Crash的数字表格 [https://www.luogu.org/show/P1829][4] 【Luogu】GCD https://www.luogu.org/problemnew/show/P2568 【Luogu】Hillan and the girl https://vjudge.net/problem/HDU-5663 ###**2、刷提高** 【BZOJ】完全平方数 https://ruanx.pw/bzojch/p/2440.html 【COGS】jzptab http://cogs.pro:8080/cogs/problem/problem.php?pid=2031 【HDU】Mophues https://vjudge.net/problem/HDU-4746 【HDU】Code https://vjudge.net/problem/HDU-5212 【Luogu】YY的GCD https://www.luogu.org/problemnew/show/P2257 【COGS】[BZOJ4407]于神之怒加强版[http://cogs.pro:8080/cogspid=2156][5] ###**3、变态题** 【Luogu】P3327 [SDOI2015]约数个数和（[我的题解][6]） [https://www.luogu.org/3327][7] 【SNMOJ】[安师大]sanrd（[我的题解][8]） http://172.40.26.251/contest/55/problem/290 ##**三、做题经验** ###**1、Mobius求解以下问题** $A、$[\[POI2007\]ZAP-Queries][9]（[题解戳我][10]） 　　$O(\sqrt{n})$求下式（预处理$O(n)$，还有拓展到$n$个$sigma$的[Visible Lattice Points][11]） $$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==k]$$ $B、$[Gcd之和][12]（[题解戳我][13]） 　　$O(n)$求下式（[jzptab][14]要求单次询问$O(\sqrt{n})$，[题解戳我][15]） $$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$$ $C、$[Crash的数字表格][16]->单次$O(n)$求下式 　　[jzptab][17]->单次$O(\sqrt{n})$求下式（[题解戳我][18]） $$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$$ $D、$[Mophues][19]（[题解戳我][20]/[题解戳我][21]） 　　$O(n\sqrt{n})$预处理并单次$O(\sqrt{n})$求下式，$Fact(i)$表示$i$唯一分解后不同质因子的个数 $$\sum_{i=1}^{n}\sum_{j=1}^{m}[Fact(gcd(i,j))<=P]$$ $E、$[Code][22]（[题解戳我][23]） 　　构造函数单次$O(n\sqrt{n})$求下式，$A$为给定的一个数列，$A[i]<=1w$ $$\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(A[i],A[j])*(gcd(A[i],A[j])-1)$$ $F、$[约数个数和][24]（[题解戳我【自己写的】][25]） 　　$O(n)$预处理并单次询问$O(\sqrt{n})$处理下式，$d(i)$为$i$的约数个数详见引理$B$$$\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$$ $G、$[YY的GCD][26]（[题解戳我][27]） 　　$O(n)$预处理并单次询问$O(\sqrt{n})$处理下式$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)为质数?1:0]$$ $H、$[Hillan and the girl][28]（[题解戳我][29]） 　　$O(n)$或$O(nloglogn)$预处理并单次询问$O(\sqrt{n})$$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)为完全平方数?1:0]$$ $I、$[于神之怒加强版][30]（[题解戳我][31]） 　　$O(n)$预处理并单次询问$O(\sqrt{n})$$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k$$ $J、$[数字表格][32]（[题解戳我][33]） 　　$O(nloglogn)$预处理并且单次询问$O(\sqrt{n})$，其中$Feb(i)$表示斐波那契数列第i项，$Feb(0)=0,Feb(1)=1...$$$\prod_{i=1}^{n}\prod_{j=1}^{m}Feb(gcd(i,j))$$ ###**2、小套路** $A、\mu$只会用到$min(N,M)$所以筛的时候可以不用筛到$MAXN$(助力冲榜) $B、$数论分块套路（当数论分块会比较麻烦的时候可以用$Map$） $C、$提$gcd$套路（把$gcd$换成字母$d$，从枚举$i，j$改成枚举$d$） $D、$**提贡献套路(换元思想)**： 　　令$T=id$然后把里面的$sigma$提取到外面，统计贡献 $E、$构造函数套路([Code][34])，不过不常用也很难想 $F、$**线性筛积性函数**，详见另一篇笔记《[积性函数与线性筛][35]》 ###**3、注意事项** $A、$数据范围大的时候注意**随时取模**！！ $B、$有时候卡空间/时间，那么能用$int$尽量$int$，**随时$1LL$** ###**４、引理** $A、$$$\lfloor{\frac{\frac{n}{i}}{d}}\rfloor=\lfloor{\frac{n}{id}}\rfloor$$　　令$n=a*(id)+b$，$b < id$ 　　那么$\lfloor\frac{n}{i}\rfloor=a*d+\lfloor\frac{b}{i}\rfloor,\lfloor\frac{b}{i}\rfloor< d$ 　　$\lfloor{\frac{\frac{n}{i}}{d}}\rfloor=a=\lfloor{\frac{n}{id}}\rfloor$ 　　 $B、$$$d(nm)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==1]$$ 　　$d(x)$表示$x$的约数个数，如$d(6)=4$ 　　任意$nm$的约数可以表示为$i*\frac{m}{j}$ 　　如果$gcd(i,j)!=1$，可以令$i=k_1p,j=k_2p$，$i*\frac{m}{j}$表示的约束是$\frac{k_1}{k_2m}$，但是我们可以发现当$i=k_1,j=k_2$的时候就已经统计过这个约数了，再不懂可以手玩$4*6$ ##**有关原创文章** 《[线性筛][36]》 《[<约数个数和>题解][37]》 《[<安师大sanrd>题解][38]》 [1]: https://www.luogu.org/problemnew/show/2261 [2]: https://www.luogu.org/problemnew/show/3455 [3]: https://www.luogu.org/problemnew/show/P2522 [4]: https://www.luogu.org/problemnew/show/P1829 [5]: http://cogs.pro:8080/cogs/problem/problem.php?pid=2156 [6]: https://www.zybuluo.com/xzyxzy/note/1023694 [7]: https://www.luogu.org/problemnew/show/3327 [8]: https://www.zybuluo.com/xzyxzy/note/1026239 [9]: https://www.luogu.org/problemnew/show/3455 [10]: http://www.cnblogs.com/cjyyb/p/7954500.html [11]: https://vjudge.net/problem/ZOJ-3435 [12]: https://oj.changjun.com.cn/problem/detail/pid/2512 [13]: http://www.cnblogs.com/cjyyb/p/8260593.html/oj.changjun.com.cn/problem/detail/pid/2512 [14]: https://vjudge.net/problem/UVA-11426 [15]: http://www.cnblogs.com/zhoushuyu/p/8284296.html [16]: https://www.luogu.org/problemnew/show/P1829 [17]: http://cogs.pro:8080/cogs/problem/problem.php?pid=2031 [18]: http://www.cnblogs.com/zhoushuyu/p/8249801.html [19]: https://vjudge.net/problem/HDU-4746 [20]: http://www.cnblogs.com/zhoushuyu/p/8287537.html [21]: http://sycstudio.com/archives/156 [22]: https://vjudge.net/problem/HDU-5212 [23]: http://sycstudio.com/archives/169 [24]: https://www.luogu.org/problemnew/show/P3327 [25]: https://www.zybuluo.com/xzyxzy/note/1023694 [26]: https://www.luogu.org/problemnew/show/P2257 [27]: http://www.cnblogs.com/cjyyb/p/8287580.html [28]: https://vjudge.net/problem/HDU-5663 [29]: http://www.cnblogs.com/zhoushuyu/p/8296010.html [30]: http://cogs.pro:8080/cogs/problem/problem.php?pid=2156 [31]: http://www.cnblogs.com/cjyyb/p/8266725.html [32]: https://www.luogu.org/problemnew/show/P3704 [33]: http://www.cnblogs.com/cjyyb/p/8274191.html [34]: https://vjudge.net/problem/HDU-5212 [35]: https://www.zybuluo.com/xzyxzy/note/1021555 [36]: https://www.zybuluo.com/xzyxzy/note/1021555 [37]: https://www.zybuluo.com/xzyxzy/note/1023694 [38]: https://www.zybuluo.com/xzyxzy/note/1026239