【数学】莫比乌斯反演

· · 个人记录

莫比乌斯反演及欧拉函数例题整理例题整理

标签： 数学

前言

本篇文章建议配合数学筛法和各种函数的定义及性质使用，不需要一开始学完所有的基础知识，只需要从零开始看题就行了，一般自己掌握过得莫反等题目都会做，如果自己不会的就表明有些性质和定义还没有学到过，直接现学性质和定义来求解即可，理论与实践同时间发生效率是最高的。

做题心得

套路

例如像这样的

\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{\gcd(i,j)}

下面那个 \gcd(i,j) 可以化作是：

\sum_{d=1}^n\sum_{i|n}\sum_{j|n}\frac{ij}{d}[\gcd(i,j)=d]

这个其实就是转换了枚举的顺序，原本是枚举 i,j 来确定 \gcd 的值，现在是直接枚举 \gcd 的值，来寻找贡献一共有多少，明显看出这是一个样的。

例如下面的：

\sum_{d}^n\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]

看后面两项其实就是

\sum_{d}^n\lfloor \frac{n}{d}\rfloor\lfloor \frac{m}{d}\rfloor

P3455 莫比乌斯反演入门题

题意：求出

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

这里为了方便，暂且把原题中的 d 做为 k ,d 的定义详见莫比乌斯反演

推导如下：

\text{首先操作}a<b \sum_{i=1}^{a/k}\sum_{j=1}^{b/k}[gcd(i,j)=1] \text{首先在这里做一下这个为什么会这样/k的解释} \text{k相当于把 1-a 中所有的数全部除k，那么他们两两之间所有的 gcd 就相当于全部 /k} \text{那么既然是因子全部除了一个 /k 就相当于 原本gcd(i,j)=k的全部/k} \text{所以就相当于在这些除完了的数中找 gcd(i,j)=1}的即可 \sum_{x=1}^{a/k}\sum_{j=1}^{b/k}\sum_{d|gcd(i,j)}\mu(d) \text{推导到这个地方可以发现} d\leq a/k,\text{可以转换一下变成} \sum_{d=1}^{a/k} \mu(d)\sum_{i=1}^{a/k}[\ d|i\ ]\sum_{j=1}^{b/k}[\ d|j\ ] \text{至于为什么会化成这种形式，首先看上上面的式子，贡献与d密切相关} \text{那么保证d有意义的前提是，i,j中的因子必须会有d才能有贡献，否则肯定不会有} \text{所以只需要知道d可以做多少次i,j因子就可以了} \text{回看上式，因为d|gcd(i,j)} \text{所以d|i,d|j 所以只考虑与这些有贡献的即可} \text{可以考虑用整除分块来简化} a/k \text{中可以被} d \text{整除的有} \frac{a/k}{d}\text{个数} \sum_{d=1}^{a/k} \mu(d)\times \lfloor\frac{a}{dk}\rfloor\times \lfloor\frac{b}{dk} \rfloor \text{可以发现能用整除分块，维护一下}\mu\text{的前缀和，然后后面的用整除分块降低时间复杂度即可}

代码

P2158 生活中的莫反GCD题目

看这张非常美丽清晰大方的图片，就是多画了一行就很离谱=_=。

我们可以发现一个很优美的性质，每一个能看到的点的横纵坐标互质，那么现在就可以愉快地猜测一番了：

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

为什么是 n-1 ？因为看一看性质就出来了，首先左下角哪一位是不计数的，因为考虑到是图的关系，所以会跟数有一些不同的地方。

然后注意一个坑点，那就是你还需要多加上 2 有没有看见最左边和最下边那两个小点，那两个是不计数的，所以你要加上去。

代码大家都会自己默写了/cy

P2522 大力容斥的模板题

题目：求：

\sum_{i=a}^{b}\sum_{j=c}^{d}[\text{gcd}(i,j)=k]

和上个题是一样的，只是用容斥去解决了

\text{设}\text{calc(a,b,k)}=\sum_{i=1}^{l}\sum_{j=1}^{r}[\text{gcd}(i,j)=k] \text{那么原式就可以化为} \text{calc(b,d,k)-calc(a-1,d,k)-calc(b,c-1,k)+calc(a-1,c-1)} \text{结束}

P2257 YY的GCD

一个不可言喻的题目，反正就nm很牛逼

首先让我们求的是 (n\leq m)

\sum_{k\in prime}^{}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]
\text{根据前两个题的经验直接化为} \sum_{k\in prime}\sum_{d=1}^{n/k}\mu(d)\times\lfloor\frac{n}{dk}\rfloor\times \lfloor \frac{m}{dk}\rfloor \sum_{k=1}^{n}\sum_{d=1}^{n/k}\mu(d)\times \lfloor \frac{n}{dk}\rfloor\times \lfloor \frac{m}{dk}\rfloor(k\in \operatorname{prime}) \text{设T=dk} \sum_{k=1}^{n}\sum_{d=1}^{n/k}\mu(d)\times \lfloor \frac{n}{T}\rfloor\times \lfloor \frac{m}{T}\rfloor (k\in \operatorname{prime}) \text{考虑把} \sum_{k=1}^{n} \text{换为}\sum_{T=1}^n,\text{发现}d \text{只在[1,n/k]的范围内，所以直接代换化为} \sum_{T=1}^{n}\lfloor \frac{n}{T}\rfloor \times \lfloor \frac{m}{T} \rfloor\times \sum_{k|T}^{k\in prime}\mu(\frac{T}{k})

至于为什么可以化成这样，可以考虑本来d的取值范围，这样化简以后他是不变的

前面的没啥为问题，后面的可以看出来能进行预处理

代码

P2568 同类型题中的欧拉和莫反解法

其实看这个题和上面的题目几乎是一模一样的，但是他的数据范围变得更加单一了，但是瞥一眼他的时间限制只有 1s 那么肯定不能 O(n) 预处理 \mu 函数来求解了，只能另寻他法。

那么只能另外找思路求解了，先把式子写出来再说

\sum^{k\in prime}_{k\leq n}\sum_{i=1}^n \sum_{j=1}^{n}[\operatorname{gcd}(i,j)=k] \sum^{k\in prime}_{k\leq n}\sum_{i=1}^{n/k} \sum_{j=1}^{n/k}[\operatorname{gcd}(i,j)=1]

通过看着上面这个上面这个式子，我们突然有一个新思路，因为(i,j) 和 (j,i) 都会被算到，所以只需要在 i>j 的时候计算出来个数乘上 2 最后在减去重复的 (1,1) 即可。

\sum^{k\in prime}_{k\leq n}\left(\sum_{i=1}^{n/k} \left( 2\sum_{j=1}^{i}[\operatorname{gcd}(i,j)=1] \right)-1 \right)

继续看一看这个最里面的式子，其实他的含义就很明显了，继续反观 \varphi 的定义式：

\varphi(m)=\sum_{i=1}^m [\operatorname{gcd}(i,m)=1]

整体代换一下就是：

\sum^{k\in prime}_{k\leq n}\left( 2\sum_{i=1}^{n/k} \varphi(i) -1 \right)

预处理一下 \varphi 的前缀和就可以了

代码

P2398 欧拉函数性质应用

该题需要求的是：

\sum_{i=1}^n \sum_{j=1}^n \operatorname{gcd}(i,j)

根据欧拉函数的性质:

\operatorname{gcd}(i,j)=\sum_{d|\operatorname{gcd}(i,j)}\varphi(d)

可以把柿子化简为：

\sum_{i=1}^n\sum_{j=1}^n\sum_{d|\operatorname{gcd}(i,j)}\varphi(d) \sum_{d=1}^n\varphi(d) \sum_{i=1}^n [\ d|i\ ]\sum_{j=1}^n [\ d|j\ ] \sum_{d=1}^n\varphi(d) \times \lfloor \frac{n}{d}\rfloor\times \lfloor \frac{n}{d}\rfloor

一眼看出这是一个非常美丽的整除分块的形式，预处理一下 \varphi(d) 的值以及前缀和，整除分块求解即可。

代码

P1390 欧拉函数基础应用

图中黑色部分正是我们要求的范围，转换成数学语言即是

\sum_{i=1}^n \sum_{j=i+1}^n\operatorname{gcd}(i,j)

通过图来看其实可以有一个很大的发现，中间就是一个\sum_{i=1}^n

左右两边是对称的，所以减去主对角线除以二就是答案

\frac{\sum_{i=1}^n\sum_{j=1}^n\operatorname{gcd}(i,j)-\sum_{i=1}^n}{2} \frac{\sum_{i=1}^n\sum_{j=1}^n\sum_{d|\operatorname{gcd}(i,j)}\varphi(d)-\sum_{i=1}^n}{2} \frac{\sum_{d=1}^n\varphi(d)\times \lfloor \frac{n}{d}\rfloor^2-\sum_{i=1}^n}{2}

通过一系列转化，就可以干掉它了

P3704 标题，向着累乘进发

题意：求：

\prod_{i=1}^n\prod_{j=1}^mf_{\operatorname{gcd}(i,j)}

其实根据他的定义和套路就可以把它化成

\prod_{d=1}^n f_d^{\sum_{i=1}^n\sum_{j=1}^m[\operatorname{gcd}(i,j)=d]}

清晰易懂，就是把累乘换成了把所有gcd(i,j)=d的全部乘起来再继续累乘，都是一个概念，看上面的幂数通过前面的经验可以非常清晰地化为

\prod_{d=1}^nf_d^{\sum_{d=1}^{n/d}\mu(d)\times\lfloor \frac{n}{kd}\rfloor\times \lfloor \frac{m}{kd} \rfloor}

这么一看貌似可以做了，但是显然时间复杂度太高了，所以考虑用换元法优化它，设 T=dk,貌似和上面的题有相似之处了。我们可以发现 k 的取值只在 [1,n/k] 中，那么就直接把 T 提到最前面就得到了

\prod_{T=1}^n\prod_{d|T}f_d^{\mu(\frac{T}{k})\times\lfloor \frac{n}{T}\rfloor\times \lfloor \frac{m}{T} \rfloor} \prod_{T=1}^n\left(\prod_{d|T}f_d^{\mu(\frac{T}{k})}\right)^{\lfloor\frac{n}{T}\rfloor\times \lfloor \frac{m}{T} \rfloor}

发现中间的一部分可以进行预处理，那么就可以直接做了。

那么这个式子为什么可以化成这种形式呢，首先我们把 T 提出来放到了最前面，其次，我们知道我们要枚举 d 那么再加上一个累乘，就可以像上面一样枚举他了，因为 T 是 k,d 的乘积，所以枚举的时候一定会把所有需要的 d 取遍

代码

P3312 \mu 与 \sigma 的结合体

简化题意：即为求：

\sum_{i=1}^{\operatorname{min}(n,a)} \sum_{j=1}^{\operatorname{min}(m,a)} \sigma(\operatorname{gcd(i,j)})

为了简便先来想想这个怎么做：

\sum_{i=1}^n \sum_{j=1}^m \sigma(\operatorname{gcd(i,j)})

考虑每一个值的贡献

\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \sigma(d)[\operatorname{gcd}(i,j)=d] \sum_{d=1}^n\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sigma(d)[\operatorname{gcd(i,j)=1}] \sum_{d=1}^n\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sigma(d)\sum_{k|gcd(i,j)}\mu(k) \sum_{d=1}^n \sigma(d)\sum_{k=1}^{n/d}\mu(k)\times \lfloor \frac{n}{dk}\rfloor\times \lfloor \frac{m}{dk}\rfloor

推到这个地方，我以为筛完 \sigma 就做完了，翻了翻第一篇题解，一样！一样！一样！草！

最后一步的换元依旧是一个牛逼问题，还是太弱了

设 T=dk

\sum_{T=1}^n \left( \sum_{d|T}\sigma(d) \times \mu(\frac{T}{d})\right)\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor

那么退完了柿子，现在思考一下如何预处理它，很明显，这个括号括的非常有水平，把里面的部分当做一个整体进行预处理就好了。

看一看这里面的一大堆柿子，只有当 d\leq a 的时候才会有贡献，不然就超出范围了，所以可以根据 a 的范围变化进行动态的修改，因为只有单点修改和区间查询，所以树状数组就是最好的选择。

为了节省时间，选择用离线处理的方法来做/cy

代码

P3327 约数和函数 d 与 \mu 结合

题意

求：

\sum_{i=1}^n\sum_{j=1}^m d(ij),\text{其中d(n)为n的约数个数}

因为是SDOI的省选题,那首先讲一下部分分（50pts）的做法：

可以考虑现行筛出每个数的约数个数，进行暴力求解，跑得还可，但是数组存不下qwq。

继续考虑如何化简式子求正解。

这里可以给出一个结论，对推式子很有帮助：

d(ij)=\sum_{x|i}\sum_{y|j}[\operatorname{gcd}(i,j)=1]

根据这个式子化简一下就是：

\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\operatorname{gcd}(x,y)=1]

化到这个地方，不要着急把最后一项给化了，先留着，看看是否对化简有帮助。

在这个地方考虑一个经典的套路，转换枚举顺序首先分别枚举 i,j 的因子 x,y。

\sum_{x=1}^n\sum_{y=1}^m\lfloor \frac{n}{x}\rfloor\lfloor \frac{m}{y}\rfloor[\operatorname{gcd}(x,y)=1]

在这个地方详细解释一下上式的由来，其实我们就是把 x,y 的枚举顺序提前，然后直接计算出 x,y 分别能起作用的个数，也就是两个 \sum 后面的式子，就是可以算出使当前 x,y 可以发挥作用的 i,j 有多少个。顺序变换，但是最后结果依旧是不重不漏的，感性理解一下即可，接下来继续化式子，上面的式子看着太不舒服了qwq。

\sum_{i=1}^n\sum_{j=1}^m\lfloor \frac{n}{i}\rfloor\lfloor \frac{m}{j}\rfloor [\operatorname{gcd}(i,j)=1]

化到这一步表示基础已经讲完了，接下来就到了真正的反演环节了，首先上一个性质。

对于两个数论函数 f(n),g(n) 来说，有以下的公式：

如果有 f(n)=\sum_{d|n}g(d),则有 g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})。

如果有 f(n)=\sum_{n|d}g(d),则有 g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)。

有了这两个性质就可以进行反演了(>w<)。

设 g(x)=\sum_{i=1}^n\sum_{j=1}^m\lfloor \frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\operatorname{gcd}(i,j)=x]。

设 f(x)=\sum_{x|d}g(d)。

可以得到：

f(x)=\sum_{i=1}^n\sum_{j=1}^m\lfloor \frac{n}{i}\rfloor\lfloor \frac{m}{j}\rfloor[x|\operatorname{gcd}(i,j)]

根据设的函数中 x|d 的条件可以转化为以下形态，也就是只有当 [x|\operatorname{gcd}(i,j)]=1 时，式子才有贡献。

将 x 除掉，就变成了

f(x)=\sum_{i=1}^{n/x}\sum_{j=1}^{m/x}\lfloor \frac{n}{ix}\rfloor\lfloor \frac{m}{jx}\rfloor[1|\operatorname{gcd}(i,j)]

很明显的，可以把后面那一坨去掉得到：

f(x)=\sum_{i=1}^{n/x}\sum_{j=1}^{m/x}\lfloor \frac{n}{ix}\rfloor\lfloor \frac{m}{jx}\rfloor f(x)=\sum_{i=1}^{n/x}\lfloor \frac{n}{ix}\rfloor\sum_{j=1}^{m/x}\lfloor\frac{m}{jx}\rfloor

现在利用反演的性质，将柿子反演一波(根据我们的定义，在题目中我们最后需要求的是 g(1)）。

g(1)=\sum_{1|d}\mu(\frac{d}{1})f(d)

最后的出来的式子即为：

g(1)=\sum_{d=1}^n\mu(d)f(d)

看一眼 f(x) 的式子，可以整除分块来预处理\sum_{i=1}^n\frac{n}{i}，然后筛出 \mu 函数，前缀和预处理，整除分块求解，时间复杂度可以通过此题。

代码实现（见博客题解）

P1829 简单的LCM问题

题意：求：

\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)

还是根据套路去做题：

\sum_{i=1}^n\sum_{j=1}^m \frac{ij}{\operatorname{gcd(i,j)}}

套路式地把 \operatorname{gcd} 放到前面去

\sum_{d=1}^n\frac{1}{d}\sum_{i=1}^n\sum_{j=1}^mij[\gcd(i,j)=d] \sum_{d=1}^nd\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ij[\gcd(i,j)=1]

此时并不需要着急把 \gcd(i,j) 换出去，可以拆开来一个个化简。

首先先看除了 \sum_{d=1}^n 右边的所有式子，当然先化作一个普遍意义下的看就好了，至于计算因为只有两个变量，所以就直接带进去两个变量区计算就好啦。

\sum_{i=1}^n\sum_{j=1}^m ij[\gcd(i,j)=1] \sum_{i=1}^n\sum_{j=1}^nij\sum_{d|\gcd(i,j)}\mu(d) \sum_{d=1}^n\mu(d)\sum_{d|i}^n\sum_{d|j}^m ij

除上两个 d 的出来

\sum_{d=1}^{n}\mu(d)\times d^2\sum_{i=1}^{n/d}\sum_{j=1}^{m/d} ij \sum_{d=1}^n\mu(d)\times d^2\frac{(n/d)(n/d+1)}{2}\times \frac{(m/d)(m/d+1)}{2}

那么最后可以用三个式子来非常清晰地描述计算过程：

\sum_{d=1}^n d \times f(n/d,m/d) f(n,m)=\sum_{d=1}^n\mu(d)\times d^2 \times g(n/d,m/d) g(n,m)=\frac{n(n+1)}{2}\times \frac{m(m+1)}{2}

整除分块预处理 f(n,m) 的左半部分，然后其他的都用函数计算然后一步步出结果就行了

大概会用到一个区间 [i,j] 中求和的式子：

\frac{r(r+1)}{2}-\frac{(l-1)l}{2}=\frac{r^2+r-l^2+l}{2}

代码

P3911 任意最小公倍数

给定一个数列 \langle A_1,A_2,A_3,A_4,…,A_N\rangle ,求：

\sum_{i=1}^n\sum_{j=1}^n \operatorname{lcm}(A_i,A_j)

经典套路走起(m 为值域)：

\sum_{i=1}^m\sum_{j=1}^m\frac{i\times j}{\gcd(i,j)}\times c_i\times c_j \sum_{d=1}^m\sum_{i=1}^m\sum_{j=1}^m\frac{i\times j}{d}[\gcd(i,j)=d]\times c_i\times c_j \sum_{d=1}^m\sum_{i=1}^{m/d}\sum_{j=1}^{m/d}i\times j\times d \times c_{id}\times c_{jd}\times [\gcd(i,j)=1] \sum_{d=1}^m\sum_{i=1}^{m/d}\sum_{j=1}^{m/d}\sum_{k|gcd(i,j)}\mu(k)\times i\times j\times d\times c_{id}\times c_{jd} \sum_{d=1}^m\sum_{k=1}^{m/d}\sum_{i=1}^{m/dk}\sum_{j=1}^{m/dk}\mu(k)\times i\times j\times d\times k^2\times c_{idk}\times c_{jdk}

单分出来看：

\sum_{i=1}^{m/dk}\sum_{j=1}^{m/dk}i\times j\times c_{idk}\times c_{jdk}

可以看出其实就是个对称的，所以就变成了：

\left(\sum_{i=1}^{m/dk}i\times c_{idk}\right)^2

设 T=dk :

\sum_{T=1}^{m}T\left(\sum_{k|T}k\times \mu(k)\right)\left(\sum_{i=1}^{m/T}i\times c_{iT}\right)^2

中间的预处理一下，右边的直接暴力算就可以了，亲测可过

代码