零基础莫反入门

· · 个人记录

前置知识：欧拉函数，线性筛，整除分块。

莫反最终公式：\mu*I=\epsilon，其中*为狄利克雷卷积。

换成数学语言为:\sum_{d|x}\mu(d)=[x=1]。

应用：

例题一：P2158 [SDOI2008]仪仗队

求\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1]

对于这个题我们发现，在最后有一个[x=1]的形式，那么我们使用莫比乌斯反演，把式子变成\sum_{i=1}^n\sum_{j=1}^n\sum_{d|gcd(i,j)}\mu(d)

我们发现d是i和j最大公因数的因数，那么d一定是i和j共同的因数。

也就是d|gcd(i,j)等价于d|i,d|j

也就是i和j都是d的倍数。

那么原式就变成\sum_{d=1}^n\mu(d)\sum_{d|i,1\le i \le n}\sum_{d|j,1\le j \le n}1

也就是\sum_{d=1}^n\mu(d)[\frac{n}{d}]^2

线性筛\mu+整除分块即可。

例题二：P3455 [POI2007]ZAP-Queries

求\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)==k]

这个题就是在上一个题的基础上把1变成了k，那么这样我们就不能莫比乌斯反演了。怎么办呢？

我们可以枚举ik和jk,这样我们只需要满足i和j互质，就可以转化为上一题的做法了。

最终式子:\sum_{d=1}^{\frac{n}{k}}\mu(d)[\frac{n}{kd}][\frac{m}{kd}]

例题三：P2398 GCD SUM

求\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)

这个题并没有之前那两个简单，但是我们可以把这个题转化成之前的两个题目。

\sum_{i=1}^n\sum_{j=1}^ngcd(i,j) =\sum_{p=1}^{n}\sum_{i=1}^n\sum_{j=1}^np[gcd(i,j)=p] =\sum_{p=1}^{n}p\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=p]

我们发现后面的式子就是第二题。

故原式=\sum_{p=1}^{n}p\sum_{d=1}^{n/p}\mu(d)[\frac{n}{pd}][\frac{m}{pd}]

这个时候我们用一个整除分块套整除分块就可以O(n)完成。

但是这样的代码长度太长了，难度太高了。

我们接下来使用一种有关线性筛的方法来计算，这种方法支持O(n+T\sqrt n)的时间复杂度多次查询。

我们把p和d交换一下：

=\sum_{p=1}^{n}p\sum_{d=1}^{n/p}\mu(d)[\frac{n}{pd}][\frac{m}{pd}] =\sum_{d=1}^{n}\sum_{p=1}^{n/d}p\mu(d)[\frac{n}{pd}][\frac{m}{pd}]

我们做一个换元：T=pd来换掉d，则满足p|T。

则原式=\sum_{T=1}^{n}\sum_{p|T}p\mu(T/p)[\frac{n}{T}][\frac{m}{T}]

=\sum_{T=1}^{n}[\frac{n}{T}][\frac{m}{T}]\sum_{p|T}p\mu(T/p)

我们发现里面的一个求和是狄利克雷卷积，为id*\mu=\varphi

所以原式=\sum_{T=1}^n[\frac{n}{T}][\frac{m}{T}]\varphi(T)

可以用O(n)的时间复杂度来筛出\varphi，然后整除分块。

例题四：P2303 [SDOI2012] Longge 的问题

求\sum_{i=1}^ngcd(i,n)

这个式子虽然和我们以前的式子略有不同，但是我们依然可以用莫比乌斯反演。

首先枚举最大公因数，把它变成\sum_{p|n}p\sum_{i=1}^n[gcd(i,n)=p]

接着枚举ip,原式变成\sum_{p|n}p\sum_{i=1}^{n/p}[gcd(i,n/p)=1]

我们可以使用莫比乌斯反演，也可以直接使用\varphi的定义，得出答案是

\sum_{p|n}p\varphi(n/p)

结束。

例题五：P3704 [SDOI2017]数字表格

求\prod_{i=1}^n\prod_{j=1}^nf_{gcd(i,j)}，其中f是斐波那契数列。

我们发现f的下标是一个gcd，也就是我们可以预处理出1-n之间的斐波那契数列。

接下来考虑化简式子。

原式=\prod_{p=1}^n\prod_{i=1}^n\prod_{j=1}^nf_p^{[gcd(i,j)=p]}

我们接下来考虑连乘符号的性质。

\prod_{i=1}^n x^{f(i)}=x^{f(1)}x^{f(2)}x^{f(3)}…x^{f(n-1)}x^{f(n)}=x^{\sum_{i=1}^nf(i)}

所以原式=\prod_{p=1}^nf_p^{\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}[gcd(i,j)=1]}

=\prod_{p=1}^nf_p^{\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}\sum_{d|i,d|j}\mu(d)} =\prod_{p=1}^nf_p^{\sum_{d=1}^{n/p}\mu(d)[\frac{n}{pd}][\frac{m}{pd}]} =\prod_{d=1}^n(\prod_{p=1}^{n/d}f_p^{[\frac{n}{pd}][\frac{m}{pd}]})^{\mu(d)} =\prod_{T=1}^n(\prod_{p|T}f_p^{\mu(T/p)})^{[\frac{n}{pd}][\frac{m}{pd}]}

里面的那个连乘可以O(n\log n)预处理，外面可以整除分块。

下面我来讲一下如何O(n\log n )预处理。

首先，如果我们先枚举T再枚举p,时间复杂度为O(n \sqrt n)，但是我们可以先枚举p,再枚举p的倍数T,这样就可以做到O(n\log n)

于是这道题就可以O(n\ log n+T\sqrt n)完成了。