莫比乌斯反演-例题

由于之前那篇备忘录要是再加上例题就太长了,所以单独开了一篇
可以先看一下前一篇文章
下文中默认 $n<m$

一个常见的套路

求 $n$ 以内和 $m$ 以内互质数对个数
$$
\begin{eqnarray}
&&\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\\
&=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d) \\
&=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}^{n}\mu(d)\times [d\mid gcd(i,j)] \\
&=&\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[d\mid gcd(i, j)] \\
&=&\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[1\mid gcd(i,j)]\\
&=&\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\end{eqnarray}
$$

BZOJ2154 Crash 的数字表格

题解来自 OIWiki
在后面有自己的题解
求在模 $20101009$ 意义下
$$ \sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i,j)\qquad (n,m\leqslant 10^7) $$

易知原式等价于

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

枚举最大公因数 $d$ ,显然两个数除以 $d$ 得到的数互质

$$ \sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})=1}\frac{i\cdot j}{d} $$

非常经典的 $\gcd$ 式子的化法

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

后半段式子中,出现了互质数对之积的和,为了让式子更简洁就把它拿出来单独计算。于是我们记

$$ \text{sum}(n,m)=\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=1]\ i\cdot j $$

接下来对 $\text {sum}(n,m)$ 进行化简。首先枚举约数,并将 $[\gcd (i,j)=1]$ 表示为 $\varepsilon (\gcd (i,j))$

$$ \sum_{d=1}^n\sum_{d\mid i}^n\sum_{d\mid j}^m\mu(d)\cdot i\cdot j $$

设 $i=i’\cdot d$ , $j=j’\cdot d$ ,显然式子可以变为

$$ \sum_{d=1}^n\mu(d)\cdot d^2\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\cdot j $$

观察上式,前半段可以预处理前缀和;后半段又是一个范围内数对之和,记

$$ g(n,m)=\sum_{i=1}^n\sum_{j=1}^m i\cdot j=\frac{n\cdot(n+1)}{2}\times\frac{m\cdot(m+1)}{2} $$

可以 $\Theta (1)$ 求解

至此

$$ \text{sum}(n,m)=\sum_{d=1}^n\mu(d)\cdot d^2\cdot g(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor) $$

我们可以 $\lfloor\frac {n}{\lfloor\frac {n}{d}\rfloor}\rfloor$ 数论分块求解 $\text {sum}(n,m)$ 函数。

在求出 $\text {sum}(n,m)$ 后,回到定义 $\text {sum}$ 的地方,可得原式为

$$ \sum_{d=1}^n d\cdot\text{sum}(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor) $$

可见这又是一个可以数论分块求解的式子!

本题除了推式子比较复杂、代码细节较多之外,是一道很好的莫比乌斯反演练习题!(上述过程中,默认 $n\leqslant m$ )

时间复杂度 : $\mathcal{O(n+m)}$ (两次数论分块)

BZOJ4659 Lcm

求在模 $2^{30}$ 意义下
$$\sum_{i=1}^{A}\sum_{j=1}^{B}lcm(i,j)|\mu (gcd(i,j))|$$
设 $n=min(A,B)$
则原式可以转化为
$$
\begin{align}
&\sum_{i=1}^{A}\sum_{j=1}^{B}lcm(i,j)|\mu (gcd(i,j))| \\
=&\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{A}{n}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{n}\rfloor}|\mu(d)|\cdot(i\cdot j\cdot d)\cdot [gcd(i,j)=1] \\
=&\sum_{d=1}^{n}d|\mu(d)|\sum_{i=1}^{\lfloor\frac{A}{n}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{n}\rfloor}(i\cdot j)\cdot [gcd(i,j)=1] \\
=&\sum_{d=1}^{n}d|\mu(d)|\sum_{i=1}^{\lfloor\frac{A}{n}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{n}\rfloor}(i\cdot j)\cdot \sum_{t|gcd(i,j)}\mu(t) \\
=&\sum_{d=1}^{n}d|\mu(d)|\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2\sum_{i=1}^{\lfloor\frac{A}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{td}\rfloor}\mu(t)\cdot i\cdot j \\
=&\sum_{T=1}^{n}T\cdot\sum_{d\mid T}(\frac{T}{d})\cdot|\mu(d)|\cdot\mu(\frac{T}{d})\cdot sum(\lfloor\frac{A}{td}\rfloor)sum(\lfloor\frac{B}{td}\rfloor) \\
=&\sum_{T=1}^{n}sum(\lfloor\frac{A}{T}\rfloor)sum(\lfloor\frac{B}{T}\rfloor)\sum_{d\mid T}\mu(d)\cdot T\cdot
\mu(\frac{T}{d})\cdot(\frac{T}{d})
\end{align}
$$
其中
$$sum(x)=\frac{x(x+1)}{2}$$
前面一块可以用数论分块,后面一块可以一开始预处理
$$sum_N=\sum_{T=1}^{N}\sum_{d\mid T}\mu(d)\cdot T\cdot \mu(\frac{T}{d})\cdot(\frac{T}{d})$$
然后搭配数论分块做
总复杂度 $\mathcal{O(A\log{A}+T(\sqrt{A}+\sqrt{B}))}$

YY的GCD

设 $f(x)$ 表示 $x$ 是否为质数,则题目要求的为
$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j))$$
可以转化为枚举 $gcd$ ,然后用一贯套路
$$
\begin{eqnarray}
&&\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]\\
&=&\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t\mid gcd(i,j)}\mu(t)\\
&=&\sum_{d\in prime}^{n}\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}[1\mid gcd(i,j)] \\
&=&\sum_{d\in prime}^n\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\lfloor\frac{n}{td}\rfloor\lfloor\frac{m}{td}\rfloor\\
&=&\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\cdot\lfloor\frac{m}{T}\rfloor\sum_{d\in prime,d\mid T}\mu(\frac{T}{d})
\end{eqnarray}
$$
然后可以首先对于每个 $T\leq10^7$ 预处理出 $\sum_{d\in prime,d\mid T}\mu(\frac{T}{d})$ ,在询问时对前半部分数论分块再 $\mathcal{O(1)}$ 用后半部分的前缀和求解
单次操作复杂度 $\mathcal{O(\sqrt{n})}$

BZOJ3529 数表

首先不考虑 $a$ 的限制
若设 $f(x)$ 表示 $x$ 的约数个数和,那么要求的就是
$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j)) $$
可以继续使用套路技巧枚举一下 $gcd$
$$
\begin{eqnarray}
&&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}^{n}f(d)\cdot [gcd(i,j)=d]\\
&=&\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]\\
&=&\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t\mid gcd(i,j)}\mu(t)\\
&=&\sum_{d=1}^{n}f(d)\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}[1\mid gcd(i,j)]\\
&=&\sum_{d=1}^{n}f(d)\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\cdot\lfloor\frac{n}{td}\rfloor\cdot\lfloor\frac{m}{td}\rfloor\\
&=&\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d\mid T}f(d)\cdot\mu(\frac{T}{d})
\end{eqnarray}
$$

BZOJ3994 约数个数和

又学到一个套路
设 $d(n)$ 为 $n$ 的约数个数和,求
$$\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)$$
首先需要知道
$$d(ij)=\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)=1]$$
然后可以开始化简式子
$$
\begin{eqnarray}
&&\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\\
&=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)=1]\\
&=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{t\mid gcd(x,y)}\mu(t)\\
&=&\sum_{t=1}^{n}\mu(t)\sum_{i=1}^{n}\sum_{j=1}^{m}\lfloor\frac{n}{i}\rfloor\cdot\lfloor\frac{m}{j}\rfloor\cdot[t\mid gcd(i,j)]\\
&=&\sum_{t=1}^{n}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\lfloor\frac{\lfloor\frac{n}{t}\rfloor}{i}\rfloor\lfloor\frac{\lfloor\frac{m}{t}\rfloor}{j}\rfloor\\
&=&\sum_{t=1}^{n}\mu(t)\cdot\big{(}\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\lfloor\frac{\lfloor\frac{n}{t}\rfloor}{i}\rfloor\big{)}\cdot\big{(}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\lfloor\frac{\lfloor\frac{m}{t}\rfloor}{i}\rfloor\big{)}
\end{eqnarray}
$$
此时考虑如何快速求解后面一块,即如何快速求出 $f(n)=\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$
从实际来理解的话,我们要求出的是 $n$ 中 $i$ 的倍数有多少个,如果转化为枚举倍数,那就相当于 $n$ 中每个数有多少个约数,即
$$f(n)=\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor=\sum_{i=1}^{n}d(i)$$
这时可以继续简化前面的式子为
$$
\begin{eqnarray}
&&\sum_{t=1}^{n}\mu(t)\cdot f(\lfloor\frac{n}{t}\rfloor)\cdot f(\lfloor\frac{m}{t}\rfloor)\\
&=&\sum_{t=1}^{n}\mu(t)\cdot\big{(}\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}d(i)\big{)}\cdot\big{(}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}d(j)\big{)}
\end{eqnarray}
$$
我们预处理出 $\mu$ 和 $d$ 的前缀和,然后对后面数论分块就可以解决此题了
单次询问复杂度 $\mathcal{O(\sqrt n)}$

BZOJ4816 数字表格

又是一个套路
设 $f(n)$ 表示斐波那契数列第 $n$ 项,求
$$ \prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j)) $$
这题不需要转化,可以直接做,还是挺好做的,我直接开始推了,将原式转化
$$
\begin{eqnarray}
&&\prod_{d=1}^{n}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]}\\
&=&\prod_{d=1}^{n}f(d)^{\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\lfloor\frac{n}{td}\rfloor\lfloor\frac{m}{td}\rfloor}\\
&=&\prod_{T=1}^{n}\big{(}\prod_{d\mid T}f(d)^{\mu(\frac{T}{d})}\big{)}^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}
\end{eqnarray}
$$
最后一步转化比较重要一点
转化成上面的式子后,可以对于每一个 $T\in[1,10^6]$ 预处理出 $\prod_{d\mid T}f(d)^{\mu(\frac{T}{d})}$ ,然后对于 $\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$ 数论分块,可以解决这题
总复杂度 $\mathcal{O(n\log{P}+T\sqrt{n}\log{P})}$

BZOJ2154 Crash的数字表格


$$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$$
转化一下,可以将式子写成
$$
\begin{eqnarray}
&&\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ijd\cdot[gcd(i,j)=1]\\
&=&\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum_{t\mid gcd(i,j)}\mu(t)\\
&=&\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)[t\mid gcd(i,j)]\\
&=&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}ij[1\mid gcd(i,j)]\\
&=&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}ij
\end{eqnarray}
$$
容易知道
$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij=\frac{n(n+1)}{2}\cdot \frac{m(m+1)}{2}$$
设 $sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij$ ,继续接着前面的往下推
$$
\begin{eqnarray}
&&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{td}\rfloor}ij\\
&=&\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2 \mu(t)\cdot sum(\lfloor\frac{n}{td}\rfloor,\lfloor\frac{m}{td}\rfloor)\\
&=&\sum_{T=1}^{n}sum(\lfloor\frac{n}{T}\rfloor,\lfloor\frac{m}{T}\rfloor)\sum_{d\mid T}d\cdot (\frac{T}{d})^2\mu(\frac{T}{d})\\
&=&\sum_{T=1}^{n}sum(\lfloor\frac{n}{T}\rfloor,\lfloor\frac{m}{T}\rfloor)\big{(}T\sum_{d\mid T}d\cdot\mu(d)\big{)}
\end{eqnarray}
$$
这时我们只要对每个 $T$ 预处理出 $T\sum_{d\mid T}d\cdot\mu(d)$ 的值就行了,考虑如何快速求解
设 $f(n)=\sum_{d\mid n}d\cdot\mu(d)$
实际上 $f$ 可以用线性筛筛出,具体的是
$$
f(n)=
\begin{cases}
1-n &,n\in primes \\
f(\frac{x}{p}) &,p^2\mid n\\
f(\frac{x}{p})\cdot f(p) &,p^2\nmid n
\end{cases}
$$
其中 $p$ 表示 $n$ 的最小质因子
总时间复杂度 $\mathcal{O(n+\sqrt n)}$

sys_con

OIer,常规 / 竞赛都渣得不行