首页 > 笔记 > 莫比乌斯反演总结

莫比乌斯反演总结

问题提出

我们可能会遇到一些形如

$$F(n)=\sum_{d|n}f(d)$$

的恶心函数。结果发现$f(x)$很难求,但是$F(x)$非常好求。于是就想到怎么用$F(x)$逆推一下$f(x)$。

注意:本文中没有特殊说明的话$\large \frac{a}{b}=\lfloor \frac{a}{b} \rfloor$。

ps:此文章为线下书写,用到的很多公式可能对wordpress环境不适应,如果有公式错误请在下方评论,感谢!

解决问题

莫比乌斯反演

定义

我们观察一下这个函数

$F(x)$ $f(x)$
$F(1)=f(1)$ $f(1)=F(1)$
$F(2)=f(1)+f(2)$ $f(2)=F(2)-F(1)$
$F(3)=f(1)+f(3)$ $f(3)=F(3)-F(1)$
$F(4)=f(1)+f(2)+f(4)$ $f(4)=F(4)-F(2)$

然后我们提出一个定理:

$$f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$$

这就是莫比乌斯反演

莫比乌斯函数

定义

注意到上面提出了一个$\mu(x)$函数,它是这么定义的:

1.若$x=1$,则$\mu(x)=1$

2.把$x$唯一分解,$x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$且对于$\forall k_i=1$,此时$\mu(x)=(-1)^n$

3.其他情况$\mu(x)=0$

积性函数
定义

对于正整数$n$的一个算术函数$ f(n)$,若$f(1)=1$,且当 $a,b$ 互质时$f(ab)=f(a)f(b)$,在数论上就称它为积性函数。而且积性函数的前缀和也是积性函数。

证明

1.当$\mu(a)=0$,也就是$a$有至少一个质因子出现多次,则$ab$也会出现多次,所以$\mu(ab)=0$。

2.当$\mu(a)=1,\mu(b)=1$,也就是两个都是偶数个质因子,偶+偶=偶,所以$\mu(ab)=1$。

3.当$\mu(a)=1,\mu(b)=-1$,奇+偶=奇,所以$\mu(ab)=-1$。

4.当$\mu(a)=-1,\mu(b)=-1$,奇+奇=偶,所以$\mu(ab)=1$。

线性筛

性质

对于$\forall n \in \mathbb{N}_+ $
$$
\begin{aligned}
\sum_{d|n}\mu(d)=
\left\{
\begin{aligned}
1 \ & (n=1) \\
0 \ & (n>1) \\
\end{aligned}
\right.
\end{aligned}
$$

证明

1.当$n=1$时显然成立

2.当$n \not = 1$时,把$n$分解一下$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

在$n$的因子中,$\mu$值不为零的只有所有质因子次数都为1的因子,其中质因数个数为$i$的因子个数有$C_k^i$个。

那么就有

$$\sum_{d|n}\mu(d)=C_k^0-C_k^1+C_k^2-\cdots+(-1)^kC_k^k=\sum_{i=0}^k(-1)^iC_k^i$$

然后我们又发现了牛顿老家伙的二项式定理

$$(x+y)^n=\sum_{i=0}^nC_n^ix^iy^{n-i}$$

然后令$x=-1,y=1$,就可以了。

杜教筛
莫比乌斯反演应用

假如我们要求一个

$$\sum_{i=1}^n\mu(i),n\leq 10^{11}$$

这样线性筛就直接爆了。

但我们上面那个性质

$$\sum_{i=1}^n\sum_{d|i}\mu(d)=1$$

化简一下啊

$$\large \sum_{i=1}^n\sum_{j=1}^{\frac{n}{i}}\mu(j)=1,\sum_{i=1}^n\mu(i)=1-\sum_{i=2}^n\sum_{j=1}^{\frac{n}{i}}\mu(j)$$

然后就是枚举因子,递归求解。

这样的话我们就发现它的复杂度就是$O(n^{\frac{4}{3}})$

但是$n$较小的时候可以线筛啊,所以就可以分类讨论一下

我们线筛出$\leq x$的,然后再递推

$$\large O(x+\sum_{i=1}^{\frac{n}{x}}\sqrt{\frac{n}{i}})=O(x+\frac{n}{\sqrt{x}})$$

对$f(x)=x+\frac{n}{\sqrt{x}}$求导得
$$
\begin{aligned}
f'(x) &= (x)’+(\frac{n}{\sqrt{x}})’\\
&=1+\frac{(n)’\sqrt x-n(\sqrt x)’}{(\sqrt x)^2}\\
&=1+\frac{0-n\times \frac{1}{2\sqrt x}}{x}\\
&=1+\frac{-n}{2x^{\frac{3}{2}}}\\
\end{aligned}
$$
这样当$x=n^{\frac{2}{3}}$的时候大概就取到最小值了。。此时为$O(n^{\frac{2}{3}})$。

证明

我们可以试着倒推一下
$$
\large
\begin{aligned}
&\ \ \ \ \sum_{d|n}\mu(d)F(\frac{n}{d})\\
&=\sum_{d|n}\mu(d)\sum_{d’|\frac{n}{d}}f(d’)\\
&=\sum_{d’|n}f(d’)\sum_{d|\frac{n}{d’}}\mu(d)\\
&=f(n)
\end{aligned}
$$
对于第二行,就是代入了一下。

第三行就是对于$f(d’)$他会出现很多次,我们就可以计算它的贡献。

因为我们枚举了所有$d$为$n$ 的因子,所有$d’$是$n \over d$的因子,所以$d’$也是$n$的所有因子。

考虑一下这个$d’|\frac{n}{d}$,它的意思就是枚举所有的$d’$是$\frac{n}{d}$的因子。但是我们反向考虑一下,对于所有的$d$也是$\frac{n}{d‘}$ 的因子。

所以我们就可以直接枚举$d|\frac{n}{d’}$来计算贡献。

然后我们就用上面$\mu$的性质直接计算。当且仅当$d’=n$的时候$d=1$,它后面的式子不为0。所以得证。

形式二

$$F(n)=\sum_{n|d}f(d) \rightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$$

证明同理。这是主要应用形式。

变形

$$\large F(x)=\sum_{d=1}^{\frac{n}{x}}f(d\times x) \rightarrow f(x)=\sum_{d=1}^{\frac{n}{x}}F(d\times x)\mu(d)$$

你可以小推一下,其实和形式二是一样的,但是约束了$n$的上界。

例题

hdu1695

地址

题意

给出$n,m,k$ ,求出$1\leq x\leq n, 1 \leq y \leq m$ 且$gcd(x,y) == k$ 的$(x,y)$的对数

题解

显然就是求$ [1,n/k] $与$ [1, m/k]$有多少数对的最大公约数是1

我们设

$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的$(x,y)$的对数

$F(d)$为满足$d|gcd(x,y),1\leq x \leq n,1 \leq y \leq m$的$(x,y)$的对数

就能得到

$$\large F(x)=\sum_{d=1}^{\frac{n}{k}}f(x\times d)$$

如何快速求出$F(x)$呢?

假如$i,j$能被$k$整除,那么就能写成$i=k\times x_1,j=k \times x_2$,那我们就要直接求有多少对$x_1,x_2$。可得

$$F(x)=\frac{n}{x}\times\frac{m}{x}$$

反演一下

$$\large f(x)=\sum_{d=1}^{\frac{n}{k}}\mu(d)F(x\times d)=\sum_{d=1}^{\frac{n}{k}}\mu(d)\frac{n}{xd} \times\frac{m}{xd}$$

这样的话$f(1)$就是答案了,但是暴力是$O(n)$的,如何优化?

我们可分块算啊!$n \over d$最多有$\sqrt{n}$个值。

证明:

1.当$1\leq d < \sqrt n$时,$d$就只有$\sqrt n$个,$n \over d$最多有$\sqrt n$个。

2.当$\sqrt n \leq d \leq n$时,由于$n \over d$小于$\sqrt n$,所以$n \over d$最多有$\sqrt n$个。

证毕。

同理的话,$m \over d$就最多有$\sqrt m$个取值。又因为取值连续,所以$n \over d$和$m \over d$它两个都不变的有$\sqrt n +\sqrt m$个。

那么对于相等的段,就可以求$\mu$的前缀和,批量计算,把复杂度优化到$O(\sqrt n+\sqrt m)$。

具体的实现的时候,假如遍历到了位置$i$,找到下一个相同位置代码为min(n/(n/i),m/(m/i))

对于$n$来说,找到最大的$j$满足

$$\frac{n}{i} \leq\frac{n}{j}$$

化简一下得到

$\large j\leq \frac{n}{\frac{n}{i}}$

对于$m$同理,求最小值就好了。

代码

这题其实是三倍经验题

luogu3455

luogu2522

就是改改容斥过程啥的。。

luogu3327

题意

有$T \leq 50000$次询问,给你$n,m \leq 50000$,求

$$\sum_{i=1}^n\sum_{j=1}^md(i,j)$$

其中$d(x)$为$x$的因子个数。

题解

先证一个弱弱的引理

引理

$$\sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left \lfloor \frac{y_i}{x_i} \right \rfloor \prod_{i < j } [gcd(x_i, x_j)=1]$$

证明

好久没有证过这么舒畅的东西了

首先对于$k=1$,就可以简化一下

$$\sum_{i}^nd(i)=\sum_{i}^n\lfloor \frac{n}{i} \rfloor[gcd(n,i)=1]$$

我们对于$n$的因子可以想一下它的贡献。它一共就计算了$n \over x$次。

现在我们对$k>1$进行归纳:

我们需要证明:

$$d_1(y_1, y_2, \cdots, y_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = f_1 (y_1, y_2, \cdots, y_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left \lfloor \frac{y_i}{x_i} \right \rfloor \prod_{i < j} [gcd(x_i, x_j)=1]$$

这样通过$y_1$来归纳一下:

当$y_1=1$时,发现是$k-1$维的证明,成立。

然后对于$y_1>1$,设一下

$$d_2(y_1, y_2, \cdots, y_k) = d_1(y_1, y_2, \cdots, y_k) – d_1(y_1-1, y_2, \cdots, y_k)$$

$$f_2(y_1, y_2, \cdots, y_k) = f_1(y_1, y_2, \cdots, y_k) – f_1(y_1-1, y_2, \cdots, y_k)$$

然后再用$y_2$归纳出$d_2=f_2$。一直做下去,直到归纳$d_{k+1}=f_{k+1}$

就需要证明这个

$$d_{k+1}(y_1, y_2, \cdots, y_k) = d(y_1 y_2 \cdots y_k) = f_{k+1}(y_1, y_2, \cdots, y_k) = \sum_{x_1|y_1} \sum_{x_2|y_2} \cdots \sum_{x_k|y_k} \prod_{i < j} [gcd(x_i, x_j)=1]$$

这样话我们就要考虑所有质因子的贡献。就可以得出了。我有一个绝妙的证明,但是懒得写

然后就直接推式子就好了
$$
\large
\begin{align}
ans& = \sum_{i=1}^{n} \sum_{j=1}^{m} d(ij) \\
& = \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{j} \right \rfloor [(i, j)=1] \\
& = \sum_{d=1}^{n} \mu(d) \sum_{i=1}^{ \left \lfloor \frac{n}{d} \right \rfloor } \sum_{j=1}^{ \left \lfloor \frac{m}{d} \right \rfloor } \left \lfloor \frac{n}{id} \right \rfloor \left \lfloor \frac{m}{jd} \right \rfloor \\
& = \sum_{d=1}^{n} \mu(d) \sum_{i=1}^{ \left \lfloor \frac{n}{d} \right \rfloor } \left \lfloor \frac{ \left \lfloor \frac{n}{d} \right \rfloor }{i} \right \rfloor \sum_{j=1}^{ \left \lfloor \frac{m}{d} \right \rfloor } \left \lfloor \frac{ \left \lfloor \frac{m}{d} \right \rfloor }{j} \right \rfloor \\
\end{align}
$$
然后就用$O(n^{1.5})$来预处理$d(x)=\sum_{i=1}^n\lfloor \frac{n}{i} \rfloor$就好了

代码

luogu3172

地址

题意

给定区间$L,R \leq 10^9$,取区间中$n \leq 10^9$个整数,使得这些数的$gcd$为$k \leq 10^9$。

题解

还是老套路

$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的方案

$F(d)$为满足$d|gcd(x,y),1\leq x \leq n,1 \leq y \leq m$的方案

可得

$$\large F(x)=\sum_{n|d}f(d)$$

考虑$F(x)$如何快速求:

对于$[L..R]$区间内的$x$倍数的个数为$d$,那么答案就是$d^n$。

那么$F(x)=(\frac{R}{x}-\frac{L-1}{x})^n$

反演

$$f(x)=\sum\limits_{x|d}\mu({d\over x})({R\over d}-{L-1\over d})^n$$

变形

$$\large f(x)=\sum_{d=1}^{r\over x}\mu(d)({{R\over x}\over d}-{{L-1\over x}\over d})^n$$

因为数据范围挺大的,直接上杜教筛。

bzoj2820

地址

或者做这道

题意

给出$n,m \leq 10^7$,$q \leq 10^4$次求$x \leq n,y \leq m,gcd(x,y)为质数$的$(x,y)$对数。

题解

感觉质数非常诡异啊,但是我们线性筛$\mu$的时候顺便筛出来了。

设$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的$(x,y)$的对数。

根据以前的:

$$f(x)=\sum_{x|d}\mu({d \over x}){n \over d}\times {m \over d} $$

那么这个题就求(以后$p$表示质数)

$$ans=\sum_{p}^{min(n,m)}f(p)=\sum_{p}^{min(n,m)}\sum_{p|d}\mu({d \over p}){n \over d}\times {m \over d}$$

令$d={d \over p}$

$$ans=\sum_{p}^{min(n,m)}\sum_{d=1}^{min(n/p,m/p)}\mu(d){n \over dp}\times {m \over dp}$$

令$T=pd$

$$ans=\sum_{p|T}\sum_{T=1}^{min(n,m)}\mu({T \over p}) {n\over T} \times {m\over T}$$

发现后面的东西都不变

$$ans=\sum_{T=1}^{min(n,m)} {n\over T} \times {m\over T}\sum_{p|T}\mu({T \over p}) $$

现在的主要问题就是求

$$d(T)=\sum_{p|T}\mu({T \over p})$$

然后整个问题就能在$\sqrt{n}$的时间内解答

我就想到了暴力,枚举每个质数,更新他的倍数。

复杂度好像还可以?

交上去就A了

luogu3312

地址

题意

令$F(x)$为$i$的约数和,$q \leq 20000$次给定$n,m \leq 10^5,a \leq 10^9$求

$$\large \sum_{1 \leq i \leq n,1\leq j \leq m, F(gcd(i,j)) \leq a} F(gcd(i,j)) \bmod 2^{31}$$

题解

我觉得$a$的限制非常的恶心啊,先不去想了。

设$f(d)$为满足$gcd(x,y)=d,1\leq x\leq n,1\leq y \leq m$的$(x,y)$的对数。

那么想都不用想了:

$$ f(x)=\sum_{x|d}\mu({d \over x}){n \over d}\times {m \over d}$$

因为是表格啊,它的$x,y$都是连续的。我们知道了每个$gcd$出现的次数,$F(x)$又可以线性筛出来,就可以化一下:
$$
\begin{align}
ans&=\sum_{i=1}^{min(n,m)}F(i)f(i)\\
&=\sum_{i=1}^{min(n,m)}F(i)\sum_{i|d}\mu({d \over i}){n \over d}\times {m \over d}\\
&=\sum_{d=1}^{min(n,m)}{n \over d}\times {m \over d}\sum_{i|d}F(i)\mu({d \over i})\\
\end{align}
$$
然后把

$$g(d)=\sum_{i|d}F(i)\mu({d \over i})$$

预处理一下就可以了。这可以用上一个题的思想,枚举$i$更新倍数。

可是还有限制啊

但是我们发现对于答案有贡献的只有$F(i)\leq a$的$i$。

于是把询问按照$a$排序,把$i$按照$F(i)$排序,每次询问把$F(i)\leq a$的$i$按照原来的方式插入。

用树状数组维护前缀和就好了。

取模直接自然溢出。

Markdown

好像都刷完了,那就完结吧。撒花


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×