莫比乌斯反演入门题目-题解

以下有几道莫比乌斯反演入门题的详尽版的题解(公式推演)。

[POI2007]ZAP-Queries

题意

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


解法1

倒一倒式子:
$$
\text{ans} = \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d]\\
=\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j)=1]\\
$$


$$
f(d) = \sum_{i=1}^{x}\sum_{j=1}^{y} [\gcd(i,j)=d]\\
$$

若:
$$
g(d) = \sum_{d|k} f(k)
$$

则可以发现 $g(d) = \lfloor \frac{x}{d} \rfloor \cdot \lfloor \frac{y}{d} \rfloor$

反演得:
$$
f(d) = \sum_{d|k} \mu(\frac{k}{d}) g(k)
$$

那么:
$$
f(1) = \sum_{k=1}^{\min(x,y)} \mu(k) g(k)
$$

所以:
$$
\text{ans} = f(1) = \sum_{k=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} \mu(k) g(k)\\
= \sum_{k=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} \mu(k) \cdot \lfloor \frac{x}{d} \rfloor \lfloor \frac{y}{d} \rfloor\\
$$

可以利用整除分块,单次查询时间时间复杂度 $O(\sqrt n)$。所以时间复杂度是 $O(n + T\sqrt n)$ 。

[HAOI2011]Problem b

题意

求:
$$
\sum_{x=a}^b \sum_{y=c}^d [gcd(x,y)=d]
$$


解法

设:
$$
\text{ans} = F(a,b,c,d) = \sum_{x=a}^b \sum_{y=c}^d [gcd(x,y)=d],\\
G(n,m) = \sum_{x=1}^n \sum_{y=1}^m [gcd(x,y)=d]
$$
利用容斥原理,可以发现这个式子可以转化成
$$
F(a,b,c,d) \\= G(b,d) - G(a-1,d) - G(b,c-1) + G(a-1,c-1)
$$
然后每一个 $G(n,m)$ 都可以按照上题的单次 $O(\sqrt n)$ 的做法求出。所以时间复杂度是 $O(n + T\sqrt n)$ 。

YY的GCD

题意

求:
$$
\sum_{i=1}^{k} \sum_{x=1}^n \sum_{y=1}^m [gcd(i,j)=p_i]\\
$$


解法1

$$
\sum_{i=1}^{k} \sum_{x=1}^n \sum_{y=1}^m [gcd(i,j)=p_i]\\
= \sum_{i=1}^k \sum_{x=1}^{\lfloor \frac{n}{p_i} \rfloor} \sum_{y=1} ^{\lfloor \frac{m}{p_i}\rfloor}
[gcd(i,j)=1]
$$


$$
f(k) = \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=k]
$$


$$
g(k) = \sum_{k|d} f(d)
= \lfloor \frac{n}{k} \rfloor \cdot \lfloor \frac{m}{k} \rfloor
$$

莫比乌斯反演得

$$
f(k) = \sum_{k|d} \mu(\frac{d}{k}) g(d)
= \sum_{i = 1}^{\lfloor \frac{\min(n,m)}{k} \rfloor}\mu(i)g(ik)\\
= \sum_{i = 1}^{\lfloor \frac{\min(n,m)}{k} \rfloor}\mu(i) \lfloor \frac{n}{ik} \rfloor \cdot \lfloor \frac{m}{ik} \rfloor
$$

所以

$$
f(1) = \sum_{i = 1}^{ \min(n,m) }\mu(i) \cdot \lfloor \frac{n}{i} \rfloor \cdot \lfloor \frac{m}{i} \rfloor
$$

则原式:

$$
\sum_{i=1}^k \sum_{x=1}^{\lfloor \frac{n}{p_i} \rfloor} \sum_{y=1} ^{\lfloor \frac{m}{p_i}\rfloor}
[gcd(i,j)=1]\\
= \sum_{i=1}^k \sum_{d=1}^{\min(\lfloor \frac{n}{p_i} \rfloor,\lfloor \frac{m}{p_i} \rfloor )}\mu(d) \cdot \lfloor \frac{n}{d p_i} \rfloor \cdot \lfloor \frac{m}{dp_i} \rfloor\\
$$

设$T_i = d p_i$,则有:
原式
$$
\sum_{i=1}^k \sum_{d=1}^{\min(\lfloor \frac{n}{p_i} \rfloor,\lfloor \frac{m}{p_i} \rfloor )}\mu(d) \cdot \lfloor \frac{n}{d p_i} \rfloor \cdot \lfloor \frac{m}{dp_i} \rfloor\\
= \sum_{i=1}^k \sum_{d=1}^{\min(\lfloor \frac{n}{p_i} \rfloor,\lfloor \frac{m}{p_i} \rfloor )}\mu(\frac{T_i}{p_i}) \cdot \lfloor \frac{n}{T_i} \rfloor \cdot \lfloor \frac{m}{T_i} \rfloor\\
= \sum_{i=1}^k \sum_{p_i | T}\mu(\frac{T}{p_i}) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor\\
= \sum_{T=1}^{\min(n,m)} \sum_{p_i|T} \mu(\frac{T}{p_i}) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor\\
= \sum_{T=1}^{\min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{p_i|T} \mu(\frac{T}{p_i}) \\
$$


$$
h(x) = \sum_{p_i|x} \mu(\frac{x}{p_i})
$$

所以原式化为:

$$
\sum_{T=1}^{\min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{p_i|T} \mu(\frac{T}{p_i}) \\
= \sum_{i=1}^{\min(n,m)} \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor h(i)
$$

只需要求出 $h(i)$ 的前缀和,我们就可以 $O(\sqrt{n})$ 整除分块算出。

观察
$$
h(x) = \sum_{p_i|x} \mu(\frac{x}{p_i})
$$

可以发现,如果我们枚举每个质数,再将所有的该质数的倍数的g[i * prime[j]] += mu[i]都加上去。

由于枚举倍数的调和级数 $\frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} = O(\ln n + r)$ ,所以这个枚举过程的复杂度是 $O(n \ln n)$ 的。

注意到这个 $h(x)$ 应当也是一个积性函数,所以事实上可以在线性素数筛的时候直接计算出 $h(x)$ 的值,这个过程就是 $O(n)$ 的。

[NOI2010]能量采集

题意

给定两个整数$n,m$,对于平面上的整点 $\{(x,y)|x \in [1,n],y \in [1,m],x,y \in \mathbb Z\}$ 。若 $(x,y)$ 与 $(0,0)$ 的连线上有 $k$ 个整点(不包括 $(0,0)$ , $(n,m)$),则产生的贡献为 $2k+1$ 。求所有满足条件的点的贡献总和。


解法

一个结论:从 $(0,0)$ 到 $(n,m)$ 的线路上,有 $\gcd(n,m)-1$ 个整点(不包括 $(0,0)$ , $(n,m)$ )。

想一想很好明白:令 $t$ 是 $n,m$ 的公因数 $(\frac {n}{t} , \frac {m}{t})$ 就相当于步长, $m,n$ 一定时 $t$ 越大,步长越小,整点就越多。 $\gcd(n,m)$ 是 $n$ ,$ m$ 的最大公因数,所以就是最多整点的个数了。

所以问题转化为:

$$
\sum_{i = 1}^{n} \sum_{j = 1}^{m}2\times \gcd(n,m)-1
$$
的值。

我们进行一些微小的变换:

$$
\sum_{i = 1}^{n} \sum_{j = 1}^{m}2\times \gcd(n,m)-1\\
= (2 \sum_{i = 1}^{n} \sum_{j = 1}^{m}\gcd(n,m)) - n \times m
$$

问题转化为求:
$$
\sum_{i = 1}^{n} \sum_{j = 1}^{m}\gcd(n,m)
$$


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

设:

$$
f(d) = \sum_{i=1}^{x} \sum_{j=1}^{y} [\gcd(i,j)=d]
$$

由第一题,可以发现:

$$
f(1) = \sum_{i = 1}^{ \min(x,y) }\mu(i) \cdot \lfloor \frac{x}{i} \rfloor \cdot \lfloor \frac{y}{i} \rfloor
$$

回代得:

$$
\text{ans} = \sum_{d=1}^{\min(n,m)} d \times (\sum_{i = 1}^{ \min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor) }\mu(i) \cdot \lfloor \frac{n}{id} \rfloor \cdot \lfloor \frac{m}{id} \rfloor)\\
$$

设 $T = id$,可以得到:
$$
\text{ans} = \sum_{d=1}^{\min(n,m)} d \times (\sum_{i = 1}^{ \min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor) }\mu(i) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor)\\
$$

改为枚举 $T$,得到:
$$
\text{ans} = \sum_{T=1}^{\min(n,m)} \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor (\sum_{d|T} \mu(\frac{T}{d}) \cdot d)
$$

如果令:
$$
h(T) = \sum_{d|T} \mu(\frac{T}{d}) \cdot d
$$

发现 $h(T)$ 是一个积性函数,所以可以 $O(n)$ 线性筛出来, 然后就可以得到:

$$
\text{ans} = \sum_{T=1}^{\min(n,m)} h(T) \cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor
$$

利用整除分块可以做到 $O(\sqrt n)$ 单次询问。

时间复杂度: $O(n + \sqrt n)$


这题亦可 $O(n \log n)$ 手动模拟容斥原理。

[国家集训队]Crash的数字表格

题意

求:
$$
\sum_{x=1}^{n} \sum_{y=1}^{m} \text{lcm}(x,y)
$$
数据范围: $n,m \leq 10^7$


解法1 $O(n)$

$$
\sum_{x=1}^{n} \sum_{y=1}^{m} \text{lcm}(x,y)\\
= \sum_{x=1}^{n} \sum_{y=1}^{m} \frac{xy}{\gcd(x,y)}
$$

我们可以枚举 $\gcd(x,y)$ 的值 $d$ ,然后就把式子化成:
$$
\sum_{x=1}^{n} \sum_{y=1}^{m} \frac{xy}{\gcd(x,y)}\\
= \sum_{d=1}^{\min(n,m)}\sum_{x=1}^{n} \sum_{y=1}^m \frac{xy}{d} [\gcd(x,y) = d]\\
= \sum_{d=1}^{\min(n,m)} d \; \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} ij[\gcd(i,j)=1]\\
$$

设:
$$
F(x,y) = \sum_{i=1}^{x} \sum_{j=1}^{y} ij[\gcd(i,j)=1]\\
$$

则:
$$
\text{ans} = \sum_{d=1}^{\min(n,m)} d \cdot F(\lfloor \frac{n}{d}\rfloor,\lfloor \frac{m}{d}\rfloor)
$$


设:
$$
h(x,y) = \sum_{i=1}^x \sum_{j=1}^y ij
= \frac{x(x+1)}{2} \cdot \frac{y(y+1)}{2}
$$

$h(x,y)$ 可以 $O(1)$ 计算得到。


我们进行莫比乌斯反演,尝试求出 $F(x,y)$ 的值:

(以下默认上界分别为 $x,y$)

$$
f(d) = \sum_{i=1}^{x} \sum_{j=1}^{y} ij[\gcd(i,j)=d],g(d) = \sum_{d|k} f(k)\\
$$

我们发现, $g(d)$ 事实上可以表示为:

$$
g(d) = d^2 \times \sum_{i=1}^{\lfloor \frac{x}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{y}{d} \rfloor} ij = d^2 \times h(\lfloor \frac{x}{d} \rfloor, \lfloor \frac{y}{d} \rfloor)
$$

经过反演:

$$
f(d) = \sum_{d|k} \mu(\frac{k}{d}) g(k)\\
= \sum_{d|k} \mu(\frac{k}{d}) \cdot k^2 \cdot h(\lfloor \frac{x}{k} \rfloor, \lfloor \frac{y}{k} \rfloor)
$$

所以:

$$
f(1) = \sum_{k=1}^{\min(x,y)} \mu(k) \cdot k^2 \cdot h(\lfloor \frac{x}{k} \rfloor, \lfloor \frac{y}{k} \rfloor)
$$

那么,
$$
F(x,y) = f(1) = \sum_{k=1}^{\min(x,y)} \mu(k) \cdot k^2 \cdot h(\lfloor \frac{x}{k} \rfloor, \lfloor \frac{y}{k} \rfloor)
$$

这个东西可以整除分块,所以我们每计算一个 $F(x,y)$ 的复杂度是 $O(\sqrt{n})$,根据:

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

我们发现,这里对于所有的 $d$ 来说, $\lfloor \frac{n}{d}\rfloor$ 与 $\lfloor \frac{m}{d}\rfloor$ 也最多分别有 $\sqrt{n}$ 个取值,所以我们最多只需要计算 $O(\sqrt{n})$ 次 $F(x,y)$ ,所以最后的时间复杂度是 $O(n)$。

解法2 $O(n + T\sqrt {n})$

我们有
$$
\text{ans} = \sum_{d=1}^{\min(n,m)} d \cdot F(\lfloor \frac{n}{d}\rfloor,\lfloor \frac{m}{d}\rfloor)
$$

又:
$$
F(x,y) = \sum_{k=1}^{\min(x,y)} \mu(k) \cdot k^2 \cdot h(\lfloor \frac{x}{k} \rfloor, \lfloor \frac{y}{k} \rfloor)\\
$$

代入得:
$$
\text{ans} = \sum_{d=1}^{\min(n,m)} d \cdot \sum_{k=1}^{\min(\lfloor \frac{n}{d}\rfloor,\lfloor \frac{m}{d}\rfloor)} \mu(k) \cdot k^2 \cdot h(\lfloor \frac{n}{dk} \rfloor, \lfloor \frac{m}{dk} \rfloor)
$$

设 $dk = T$,则有:

$$
\text{ans} = \sum_{d=1}^{\min(n,m)} d \cdot \sum_{k=1}^{\min(\lfloor \frac{n}{d}\rfloor,\lfloor \frac{m}{d}\rfloor)} \mu(k) \cdot k^2 \cdot h(\lfloor \frac{n}{T} \rfloor, \lfloor \frac{m}{T} \rfloor)
$$

枚举 $T$ ,则有:
$$
\text{ans} = \sum_{T=1}^{\min(n,m)} \sum_{d|T} d \cdot {\lfloor \frac{T}{d} \rfloor}^2 \mu(\lfloor \frac{T}{d} \rfloor) \cdot h(\lfloor \frac{n}{T} \rfloor, \lfloor \frac{m}{T} \rfloor)
$$

简单整理下:

$$
\text{ans} = \sum_{T=1}^{\min(n,m)} h(\lfloor \frac{n}{T} \rfloor, \lfloor \frac{m}{T} \rfloor) \sum_{d|T} \lfloor \frac{T}{d} \rfloor \cdot {d}^2 \mu(d)
$$

拎出来后面的一坨:
$$
f’(T) = \sum_{d|T} \lfloor \frac{T}{d} \rfloor \cdot {d}^2 \mu(d)
$$

发现这是一个积性函数,所以可以 $O(n)$ 线性筛出来,然后就可以配合整除分块 $O(\sqrt n)$ 完成单词询问。

[SDOI2015]约数个数和

题意

设 $d(x)$ 为 $x$ 的约数个数,给定 $N$ 、$M$ ,求

$$\sum^N_{i=1}\sum^M_{j=1}d(ij)$$


解法

我们有如下结论:

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

证明:

我们对 $i$ 和 $j$ 两个数做唯一分解 ,得到:
$$
i = {p_1}^{a_1} \times {p_2}^{a_2} \times \cdots \times {p_n}^{a_n}\\
j = {p_1}^{b_1} \times {p_2}^{b_2} \times \cdots \times {p_n}^{b_n}\\
$$

所以我们知道
$$
d(ij) = \prod_{x=1}^n {(a_x + b_x + 1)}
$$

我们需要证明,分别从 $i$ 和 $j$ 中选择两个互质的约数的方案数也等于上式。

我们发现,在约数的构造中,不同质因子的选取是独立的。所以我们只需要考虑一个质因子的选取方案数,然后把所有质因子做一个连乘即可。

因为不能有公共的因子,所以对 $p_1$ 这个质因子来说,我们可以正好找出 $a_1+b_1+1$ 种选取方法,分别为:

$$
(1,0),(2,0),\cdots,(a_1,0)\\
(0,1),(0,2),\cdots,(0,b_1)\\
(0,0)
$$

可以证明,这些不同的的选取可以保证我们选择的因数不会完全相同。

所以可以证明:
$$
d(ij) = \sum_{x|i} \sum_{y|j} [\gcd(x,y) = 1]
$$


原式:

$$
\sum^N_{i=1}\sum^M_{j=1}d(ij)\\
= \sum^N_{i=1}\sum^M_{j=1}\sum_{x|i} \sum_{y|j} [\gcd(x,y) = 1]\\
= \sum_{x=1}^N\sum_{y=1}^M\sum_{x|i} \sum_{y|j} [\gcd(x,y) = 1]\\
= \sum_{x=1}^N\sum_{y=1}^M [\gcd(x,y) = 1] \sum_{x|i} \sum_{y|j} 1\\
= \sum_{x=1}^N\sum_{y=1}^M [\gcd(x,y) = 1] \lfloor \frac{N}{x} \rfloor \lfloor \frac{M}{y} \rfloor\\
$$


$$
f(d) = \sum_{x=1}^N\sum_{y=1}^M [\gcd(x,y) = d] \lfloor \frac{N}{x} \rfloor \lfloor \frac{M}{y} \rfloor\\
$$


$$
g(d) = \sum_{d|i} f(i)
$$

可以发现,此时 $x,y$ 为所有 $d$ 的倍数,所以:
$$
g(d) = \sum_{i=1}^{\lfloor \frac{N}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{d} \rfloor} \lfloor \frac{N}{id} \rfloor \lfloor \frac{M}{jd} \rfloor
$$

进行一步反演:
$$
f(d) = \sum_{d|k} \mu(\frac{k}{d}) g(k)
$$

则:

$$
f(1) = \sum_{k=1}^{\min(n,m)} \mu(k) g(k)\\
= \sum_{k=1}^{\min(n,m)} \mu(k) \sum_{i=1}^{\lfloor \frac{N}{k} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{k} \rfloor} \lfloor \frac{N}{ik} \rfloor \lfloor \frac{M}{jk} \rfloor\\
= \sum_{k=1}^{\min(n,m)} \mu(k) (\sum_{i=1}^{\lfloor \frac{N}{k} \rfloor}\lfloor \frac{N}{ik} \rfloor) (\sum_{j=1}^{\lfloor \frac{M}{k} \rfloor} \lfloor \frac{M}{jk} \rfloor)\\
$$

我们发现:

$$
\sum_{x=1}^nd(x) = \sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor
$$

所以:

$$
\text{ans} = \sum_{k=1}^{\min(n,m)} \mu(k) (\sum_{i=1}^{\lfloor \frac{N}{k} \rfloor}\lfloor \frac{N}{ik} \rfloor) (\sum_{j=1}^{\lfloor \frac{M}{k} \rfloor} \lfloor \frac{M}{jk} \rfloor)\\
= \sum_{k=1}^{\min(n,m)} \mu(k) \sum_{i=1}^{\lfloor \frac{N}{k} \rfloor}d(i) \sum_{j=1}^{\lfloor \frac{M}{k} \rfloor} d(j)\\
$$

令:

$$
h(x) = \sum_{i=1}^x d(i)
$$

则:

$$
\text{ans} = \sum_{k=1}^{\min(n,m)} \mu(k) \cdot h(\lfloor \frac{N}{k} \rfloor) \cdot h(\lfloor \frac{M}{k} \rfloor)\\
$$

我们发现 $d(i)$ 是一个积性函数,可以 $O(n)$ 线性筛,然后 $h(x)$ 可以 $O(n)$ 前缀和,然后就可以 $O(\sqrt n)$ 整除分块单次出解。