我也不知道什么是"莫比乌斯反演"和"杜教筛"

　

我也不知道

upd:发现这篇文章里面似乎有很多细节上的错误，如果还有错误的话在cnblogs下评论吧，我会改的QwQ，cnblogs戳这里。

upd：正在写一篇复习向的文章，之后贴链接，可以作为这篇文章的一个补充。

upd：写好啦，戳这里。新写的这篇复习向文章QwQ，可以当做一个补充来看吧。不过新写的文章也有我新的理解吧。

Part0

最近一直在搞这些东西

做了将近20道题目吧

也算是有感而发

写点东西记录一下自己的感受

如果您真的想学会莫比乌斯反演和杜教筛，请拿出纸笔，每个式子都自己好好的推一遍，理解清楚每一步是怎么来的，并且自己好好思考。

Part1莫比乌斯反演

莫比乌斯反演啥都没有，就只有两个式子（一般只用一个）

原来我已经写过一次了，再在这里写一次

就只写常用的那个吧

基本的公式

---

对于一个函数$f\left(x\right)$f(x)

设$g\left(x\right)={\sum }_{x\mathrm{\mid }d}f\left(d\right)$g(x)=∑x∣d​f(d)

那么

$f\left(x\right)=\sum _{x\mathrm{\mid }d}\mu \left(\frac{d}{x}\right)g\left(d\right)$f(x)=x∣d∑​μ(xd​)g(d)

---

这个有什么用？

似乎太有用了一点

随手搞道题目来说吧

---

求$\sum _{i=1}^n\sum _{j=1}^m\left[gcd\right(i,j)=1]$i=1∑n​j=1∑m​[gcd(i,j)=1]

这个东西很直接，

所以我们设$f\left(x\right)=\sum _{i=1}^n\sum _{j=1}^m\left[gcd\right(i,j)=x]$f(x)=i=1∑n​j=1∑m​[gcd(i,j)=x]

$g\left(x\right)=\sum _{x\mathrm{\mid }d}f\left(d\right)$g(x)=x∣d∑​f(d)

根据莫比乌斯反演可以得到

$f\left(1\right)=\sum _{1\mathrm{\mid }d}\mu \left(\frac{d}{1}\right)g\left(d\right)=\sum _{i=1}^n\mu \left(i\right)g\left(i\right)$f(1)=1∣d∑​μ(1d​)g(d)=i=1∑n​μ(i)g(i)

$g\left(x\right)$g(x)是什么东西？

$g\left(x\right)=\sum _{i=1}^n\sum _{j=1}^m\left[x\mathrm{\mid }gcd\right(i,j\left)\right]$g(x)=i=1∑n​j=1∑m​[x∣gcd(i,j)]

直接把$x$x除到上面去

$g\left(x\right)=\sum _{i=1}^{n\mathrm{/}x}\sum _{j=1}^{m\mathrm{/}x}\left[1\mathrm{\mid }gcd\right(i,j\left)\right]$g(x)=i=1∑n/x​j=1∑m/x​[1∣gcd(i,j)]

$\left[1\mathrm{\mid }gcd\right]$[1∣gcd]显然成立的

所以$g\left(x\right)=\left[\frac{n}{x}\right]\left[\frac{m}{x}\right]$g(x)=[xn​][xm​]

可以$O\left(1\right)$O(1)计算

所以，$f\left(1\right)$f(1)可以$O\left(n\right)$O(n)计算

---

一起推下式子

莫比乌斯反演的套路太多了

我们再来看两道题目

Crash的数字表格

jzptab

这两题按照顺序看嗷

具体的过程直接看我博客里面写的东西

我们发现这两道题一模一样

但是下面的那道题目可以做到单次询问$O\left(\sqrt{n}\right)$O(n​)

他多干了什么？？？

这个问题，我们自己再来重新推一下

不过找个容易点的东西

---

$\sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j)$i=1∑n​j=1∑m​gcd(i,j)

这个肯定没有前面我给的例子的莫比乌斯反演那么直接

但是我们观察一下，$gcd$gcd的取值有哪些？？

$1\mathrm{～}n$1～n(假设$n\&lt;m$n<m)

那么，我们可以把$gcd$gcd相同的项合并

所以，我们枚举$gcd$gcd的值

$\sum _{d=1}^{n}d\sum _{i=1}^n\sum _{j=1}^m\left[gcd\right(i,j)=d]$d=1∑n​di=1∑n​j=1∑m​[gcd(i,j)=d]

后面的那一部分是不是想到了前面推出的东西？？？

所以先把$d$d直接除上去

$\sum _{d=1}^{n}d\sum _{i=1}^{n\mathrm{/}d}\sum _{j=1}^{m\mathrm{/}d}\left[gcd\right(i,j)=1]$d=1∑n​di=1∑n/d​j=1∑m/d​[gcd(i,j)=1]

$n\mathrm{/}d$n/d和$m\mathrm{/}d$m/d不要想太多，你就当成$x$x和$y$y

$\sum _{i=1}^x\sum _{j=1}^y\left[gcd\right(i,j)=1]$i=1∑x​j=1∑y​[gcd(i,j)=1]

不就是上面推过的第一个例子？？

$=\sum _{i=1}^x\mu \left(i\right)\left[\frac{x}{i}\right]\left[\frac{y}{i}\right]$=i=1∑x​μ(i)[ix​][iy​]

把这一截放回我们要求的式子里面去

$\sum _{d=1}^{n}d\sum _{i=1}^x\mu \left(i\right)\left[\frac{x}{i}\right]\left[\frac{y}{i}\right]$d=1∑n​di=1∑x​μ(i)[ix​][iy​]

把$x,y$x,y还是写成原样吧

$\sum _{d=1}^{n}d\sum _{i=1}^{n\mathrm{/}d}\mu \left(i\right)\left[\frac{n}{id}\right]\left[\frac{m}{id}\right]$d=1∑n​di=1∑n/d​μ(i)[idn​][idm​]

是不是$n\mathrm{/}d$n/d可以数论分块

而在计算后面的东西的时候，$\frac{n\mathrm{/}d}{i}$in/d​也可以数论分块？？

所以这个时候的复杂度是$O\left(n\right)$O(n)

与之相对应的就是上面Crash的数字表格的$O\left(n\right)$O(n)做法

可是，像下面那个$O\left(\sqrt{n}\right)$O(n​)是怎么做的呢？

那我们就继续推一步

我们是不是可以直接对$\frac{n}{id}$idn​分块呢？

所以，我们设$T=id$T=id把$id$id换一下

$\sum _{d=1}^{n}d\sum _{i=1}^{n\mathrm{/}d}\mu \left(i\right)\left[\frac{n}{T}\right]\left[\frac{m}{T}\right]$d=1∑n​di=1∑n/d​μ(i)[Tn​][Tm​]

这个时候，比较关键的一步

把$T$T提出来

$\sum _{T=1}^n\left[\frac{n}{T}\right]\left[\frac{m}{T}\right]\sum _{d\mathrm{\mid }T}d\mu \left(\frac{T}{d}\right)$T=1∑n​[Tn​][Tm​]d∣T∑​dμ(dT​)

为什么是这个？？

我们来分析一波

首先每一个$T$T一定对应$\left[\frac{n}{T}\right]\left[\frac{m}{T}\right]$[Tn​][Tm​]

这一项之和$T$T有关，所以可以提出来

这个时候考虑对于每一个$T$T，什么样的$i$i和$d$d会给他产生贡献呢？

最显然的一点，$d$d是$T$T的一个因数

看到上面的式子，我们不难发现会贡献一个$d$d的什么东西

后面的是什么？$\mu \left(i\right)$μ(i)

继续想想，既然$T=id$T=id，我们枚举了一个$T$T，

又知道$d$d是$T$T的一个因子了，所以$i=\frac{T}{d}$i=dT​

所以，就有了上面把$T$T拿出来的式子

前面的东西看起来可以数论分块

但是这样子后面的东西怎么办？

不可能$O\left(\sqrt{n}\right)$O(n​)暴力枚举呀

没错，当然不需要暴力枚举

我们发现后面的东西也是一个积性函数（因为他是两个积性函数的狄利克雷卷积）

所以它是可以线性的筛出来的

到这里，前面对于$T$T数论分块

后面的前缀和可以$O\left(n\right)$O(n)线性筛预处理出来

此时单次询问整体的复杂度就是$O\left(\sqrt{n}\right)$O(n​)

对了，不要思想江化

后面那个东西如果不能够直接线性筛

那就不要线性筛了，

只要复杂度允许，暴力筛也是很可以的

---

其实，如果我们继续观察，很容易知道一点：

${\sum }_{d\mathrm{\mid }T}d\mu \left(\frac{T}{d}\right)=\phi \left(T\right)$∑d∣T​dμ(dT​)=φ(T)

upd:原来底下的证明是假的，已经删掉了，这里用容斥的方法很容易证明，考虑到$\mu$μ是容斥系数就可以很容易的知道上述式子的组合意义。

我们知道$(1\ast \phi )\left(i\right)=i$(1∗φ)(i)=i

还知道$(1\ast \mu )\left(i\right)=e$(1∗μ)(i)=e

其中$1$1是$f\left(x\right)=1$f(x)=1

$e$e是$f\left(x\right)=[x=1]$f(x)=[x=1]

$id$id是$f\left(x\right)=x$f(x)=x

所以这个东西当然可以线性筛啦。

---

莫比乌斯反演差不多就到这里啦

我们经历的复杂度从$O\left(n^2\right)$O(n2)的暴力

推一步之后变成了$O\left(n\right)$O(n)

再变成了$O\left(\sqrt{n}\right)$O(n​)

莫比乌斯反演的关键步骤也就是两步

首先是化简式子，写成莫比乌斯反演的形式

然后就是怎么处理前缀和，数论分块等东西的问题

这些能够解决好，莫比乌斯反演的题目就很好解决啦

Part2线性筛

当然是怎么各种线性筛东西啦

线性筛最重要的一点：

每个数一定，也只会，被他的最小质因子给筛到

说白点，比如说$72=2\ast 2\ast 2\ast 3\ast 3$72=2∗2∗2∗3∗3

他就会被他的最小质因子给筛到

也就是$2\ast 36$2∗36时被筛到

所以，一般线性筛如果要存储其他的东西来筛的话

一定是记录最小质因子的东西

大概的写一下几个积性函数：

$\mu$μ莫比乌斯函数

这个怎么筛应该都会吧

$\phi$φ欧拉函数

怎么筛应该也很明显吧。

$d$d约数个数

这个怎么筛？

考虑唯一分解定理:

$x=\prod p_i^{ai}$x=∏piai​

那么$d\left(x\right)=\prod (ai+1)$d(x)=∏(ai+1)

记录一下最小质因子的个数

每次就先把原来的除掉，再把$+1$+1后的个数乘上就好啦

$\sigma$σ约数和

还是唯一分解定理

$x=\prod p_i^{ai}$x=∏piai​

$\sigma \left(x\right)=\prod \left({\sum }_{j=0}^{ai}{p}_i^j\right)$σ(x)=∏(∑j=0ai​pij​)

记录一下最小质因子的上面那个式子的和

以及这个因子的$ai$ai次幂

每次也是先除掉再乘上新的

$a^k$ak $k$k次幂

把这个东西写进来，只是为了提醒一下

$a^k$ak这种东西是一个完全积性函数，也是可以丢进去筛的

$inv$inv乘法逆元

没啥，一样的，乘法逆元也是完全积性函数

蛤，我知道可以$O\left(n\right)$O(n)递推

只是写一下而已

---

我比较懒，不想把板子蒯过来

直接把ppl的链接给你们嗷（虽然他的代码风格我觉得很丑）

Part3杜教筛

来个栗子

线性筛$O\left(n\right)$O(n)复杂度，美滋滋

好的，我知道了

来一个很$interesting$interesting的题目？？？

$\mathrm{求}\sum _{i=1}^n\mu \left(i\right)\mathrm{的}\mathrm{值}$求i=1∑n​μ(i)的值

我当然知道你会线性筛

所以$n\&lt;=10^9$n<=109

杜教筛是蛤？

比如说。。

我们现在要求一个积性函数$f\left(i\right)$f(i)的前缀和$S\left(i\right)$S(i)

也就是说$S\left(n\right)={\sum }_{i=1}^{n}f\left(i\right)$S(n)=∑i=1n​f(i)

现在很不好算呀

怎么办？？

这个时候，就来杜教筛套路一波

我再来找个积性函数$g\left(i\right)$g(i)（不知道是啥）

让$g$g和$f$f做一个卷积

$(g\ast f)\left(i\right)=\sum _{d\mathrm{\mid }i}g\left(d\right)f\left(\frac{i}{d}\right)$(g∗f)(i)=d∣i∑​g(d)f(di​)

再求一下卷积的前缀和

$\sum _{i=1}^n(g\ast f)\left(i\right)=\sum _{i=1}^n\sum _{d\mathrm{\mid }i}g\left(d\right)f\left(\frac{i}{d}\right)$i=1∑n​(g∗f)(i)=i=1∑n​d∣i∑​g(d)f(di​)

把$d$d给提出来

$\sum _{d=1}^{n}g\left(d\right)\sum _{d\mathrm{\mid }i}f\left(\frac{i}{d}\right)$d=1∑n​g(d)d∣i∑​f(di​)

$\sum _{d=1}^{n}g\left(d\right)\sum _{i=1}^{n\mathrm{/}d}f\left(i\right)$d=1∑n​g(d)i=1∑n/d​f(i)

$\sum _{d=1}^{n}g\left(d\right)S\left(\frac{n}{d}\right)$d=1∑n​g(d)S(dn​)

如果仔细想想

我们就会有这个式子：

$g\left(1\right)S\left(n\right)=\sum _{i=1}^{n}g\left(i\right)S\left(\frac{n}{i}\right)-\sum _{i=2}^{n}g\left(i\right)S\left(\frac{n}{i}\right)$g(1)S(n)=i=1∑n​g(i)S(in​)−i=2∑n​g(i)S(in​)

前面的东西是狄利克雷卷积

$g\left(1\right)S\left(n\right)=\sum _{i=1}^n(g\ast f)\left(i\right)-\sum _{i=2}^{n}g\left(i\right)S\left(\frac{n}{i}\right)$g(1)S(n)=i=1∑n​(g∗f)(i)−i=2∑n​g(i)S(in​)

如果狄利克雷卷积的前缀和非常好算的话

那么我们就可以对后面的东西进行数论分块

然后递归计算。

提醒一句：

一定要记忆化，一定要记忆化，一定要记忆化

回到栗子

${\sum }_{i=1}^n\mu \left(i\right)$∑i=1n​μ(i)

把杜教筛的公式套路式子找过来蛤

$g\left(1\right)S\left(n\right)=\sum _{i=1}^n(g\ast \mu )\left(i\right)-\sum _{i=2}^{n}g\left(i\right)S\left(\frac{n}{i}\right)$g(1)S(n)=i=1∑n​(g∗μ)(i)−i=2∑n​g(i)S(in​)

看到了$\mu$μ想一个积性函数，让他们的狄利克雷卷积前缀和很好算

我们知道

$\sum _{d\mathrm{\mid }i}\mu \left(d\right)=[d=1]=e$d∣i∑​μ(d)=[d=1]=e

也就是说

$(1\ast \mu )=e$(1∗μ)=e

$e$e的前缀和是啥？

当然是$1$1了

所以，取$g\left(x\right)=1$g(x)=1

$S\left(n\right)=1-\sum _{i=2}^{n}S\left(\frac{n}{i}\right)$S(n)=1−i=2∑n​S(in​)

这样子的话，首先线性筛出一部分的$\mu$μ的前缀和

然后来一波记忆化搜索美滋滋

---

再来个栗子把

把上面的$\mu$μ换成$\phi$φ

我们还是知道

$\sum _{d\mathrm{\mid }i}\phi \left(d\right)=i=id\left(i\right)$d∣i∑​φ(d)=i=id(i)

所以，如果是$\phi$φ的话

就令$g\left(x\right)=1$g(x)=1

所以，

$S\left(n\right)=\frac{n\ast (n+1)}{2}-\sum _{i=2}^{n}S\left(\frac{n}{i}\right)$S(n)=2n∗(n+1)​−i=2∑n​S(in​)

多好的套路

但是，不要被套路给套死啦

面对不同的函数

一定要考虑清楚$g$g是啥

好的$g$g能让你的程序更加好算

Part4我也不知道为什么要加上这一部分

好啦

上面好好地写了一下莫比乌斯反演和杜教筛

是不是觉得很简单

当然，莫比乌斯反演和杜教筛当然可以混在一起

莫比乌斯反演推柿子

杜教筛求前缀和

一点也不矛盾

---

既然我也不知道最后这部分干啥

那就找一堆题目来吧

欢迎查我水表

算了

还是把水表给你们把

莫比乌斯反演的水表

杜教筛的水表

---

最后，说几句话

不要因为有了杜教筛和线性筛

就天天想着怎么筛

筛不了就滚去写暴力

埃氏筛法很不错

暴力枚举因数也很不错

最后，一句最经典的话作为结尾

骗分过样例，暴力出奇迹

相关阅读