毒瘤。
一些东西的证明放在最后的。
一些约定
高斯记号
对于命题 \text{A},高斯记号
[\text{A}] =\begin{cases}1 & \text{if A is True} \\0 & \text{if A is False}\end{cases}
数论函数
对于定义域与值域均为 \mathbb{Z}^+ 的函数,称为数论函数。
莫比乌斯函数
将 x 质因数分解
x = \prod_{i = 1}^{\omega(x)} p_i^{k_i}
那么
\mu(x) =\begin{cases}1 & x = 1 \\0 & \exists k_i \geq 2 \\(-1)^{\omega(x)} &\text{otherwise}\\\end{cases}
重要结论
\sum_{d | n} \mu(d) = [n = 1] \tag{1.1}
证明见下
欧拉函数
\varphi(x) = \sum_{i = 1}^x [i \bot x]
重要结论
\sum_{d | n} \varphi(n) = n
自函数
id(x) = x
1 函数
1(x) = 1
单位元函数
e(x) = [x = 1]
这些函数都是积性的。
狄利克雷卷积
对于两个数论函数 f, g 他们的狄利克雷卷积
(f * g)(x) = \sum_{d | x} f(d) \times g(\dfrac{x}{d})
狄利克雷卷积在数论函数集上形成阿贝尔群。在积性数论函数集上形成群,且满足交换律,结合律。
把上面的两条重要性质用狄利克雷卷积来表示就是
1 * \mu = e \\1 * \varphi = id
数论分块
当 i 取遍 [1, n] 时,\Big\lfloor\dfrac{n}{i}\Big\rfloor 的值仅有 O(\sqrt{n}) 种。相同的值对应的 i 是连续的,我们称作一块。块的左端点如果为 l,右端点为
\Big\lfloor\dfrac{n}{\frac{n}{l}}\Big\rfloor \tag{1.2}
证明见下。
莫比乌斯函数的应用
套路一 交换和号
求
\sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = 1]
考虑莫比乌斯函数的性质
\sum_{d |n} \mu(d) = [n = 1]
我们把上式的 n 换做 \gcd(i, j)
\sum_{i = 1}^n \sum_{j = 1}^n \sum_{d | \gcd(i, j )} \mu(d)
一个重要的套路来了,因为 d | \gcd(i, j),所以 d | i \land d | j,这是等价的。因此 i, j 都是 d 的倍数。所以我们枚举 i, j 是 d 的几倍。并且交换和号。(下文和号的上界省略下取整符号)。
\sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^\frac{n}{d} 1 \\\sum_{d = 1}^n \mu(d) \times (\lfloor\frac{n}{d}\rfloor)^2
用线性筛筛出 \mu 并计算前缀和,再用数论分块即可 O(n) + O(\sqrt{n}) 解决问题。
再来看下一个式子
\sum_{i = 1}^{n} \sum_{j = 1}^n i \times j \times [\gcd(i, j) = 1]
虽然考虑意义我们发现这个式子明显等于 n \times \dfrac{\varphi(n)}{2},不过我们仍然可以套用莫比乌斯函数。
\begin{aligned}&= \sum_{i = 1}^n \sum_{j = 1}^n i \times j \sum_{d | \gcd(i, j)} \mu(d) \\&= \sum_{d = 1}^n \mu(d) \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^\frac{n}{d} i \times j \times d^2\ (\text{don't forget about the}\ d^2!) \\&= \sum_{d = 1}^{n} \mu(d) \times d^2 \times A^2\end{aligned}
其中 A = \dfrac{1}{2} \times \Big\lfloor\dfrac{n}{d}\Big\rfloor\times (\Big\lfloor\dfrac{n}{d}\Big\rfloor +1)。
套路二 枚举分数转换狄利克雷卷积
求
\sum_{i = 1}^n \sum_{j = 1}^n \operatorname{lcm}(i, j)
先化开来
\begin{aligned}&= \sum_{i = 1}^n \sum_{j = 1}^n \dfrac{i \times j}{\gcd(i, j)} \\&= \sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^n \dfrac{i \times j}{d} \times [\gcd(i, j) = d] \\&= \sum_{d = 1}^n \sum_{i = 1}^\frac{n}{d} \sum_{j = 1}^\frac{n}{d} i \times j \times d \times[\gcd(i, j) = 1] \\&= \sum_{d = 1}^n d\sum_{x = 1}^{\frac{n}{d}} \mu(x) \times x^2 \sum_{i = 1}^\frac{n}{dx}\sum_{j = 1}^\frac{n}{dx} i \times j\end{aligned}
按之前的套路继续推下去发现只能单次 O(n \sqrt{n}) 的复杂度解决。这里有第二个套路。枚举 T = dx。
\begin{aligned}&= \sum_{T = 1}^n \sum_{d | T} d \times \mu(\dfrac{T}{d}) \times F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times (\dfrac{T}{d})^2\\ &= \sum_{T = 1}^n F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times \sum_{d | T} d \times \mu(\dfrac{T}{d}) \times (\dfrac{T}{d})^2 \\&= \sum_{T = 1}^n T \times F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times \sum_{d | T} \dfrac{T}{d} \times \mu(\dfrac{T}{d}) \\&= \sum_{T = 1}^n T \times F(\Big\lfloor\dfrac{n}{T}\Big\rfloor)^2 \times \sum_{d | T} d \times \mu(d)\end{aligned}
(F(n) 代表 \sum_{i = 1}^n)
如果我们记 h(T) = \sum_{d | T} d \times \mu(d),会发现 h 是一个积性的函数(证明见下)。
晒出 h 来就能 O(n) + O(\sqrt{n}) 解决问题了。
莫比乌斯反演
如果式子满足:
f(n) = \sum_{d | n} g(d)
那么就有:
g(n) = \sum_{d | n} f(n) \times \mu(\dfrac{n}{d})
证明见下。
一些证明
1.1
式子等价于 1 * \mu = e。因为 1, \mu, e 这些函数都是积性的,所以只需要证明对于任意质数 p 与 k \in \mathbb{Z}^+,都有
e(p^k)=(1 * \mu)(p^k)
即可。
\begin{aligned}(1*\mu)(p^k) &= \sum_{d | p^k} 1 \times \mu(\dfrac{p^k}{d}) \\&= \sum_{d | p^k} \mu(d) \\\end{aligned}
因为 p 为质数,所以 d 一定可以表示为 p^i 的形式,且 i | k。
因为当 i \geq 2 时,对答案没有贡献。所以当 i = 1 时,贡献为 -1;i = 0 时,贡献为 1。
所以上述和式展开来写时类似
1 + (-1) + 0 + 0 \cdots + 0
的。
故当定义域为质数域质数组成的所有数(即 \mathbb{Z}^+ - \{1\}),有 1 * \mu = e。
然而我们发现,当 x = 1 时,上面的和式只会出现第一项,即 1 的那一项。所以 (1 * \mu)(1) = 1 = e(1)。
1.2
假设 i > j。
\because \Big\lfloor\dfrac{n}{i}\Big\rfloor = \Big\lfloor\dfrac{n}{j}\Big\rfloor \\\therefore \dfrac{n}{i} \geq \Big\lfloor\dfrac{n}{j}\Big\rfloor \\\therefore \dfrac{i}{n} \leq \Big\lfloor\dfrac{n}{j}\Big\rfloor^{-1} \\\therefore i \leq n \times \Big\lfloor\dfrac{n}{j}\Big\rfloor^{-1}
套路二的积性函数
对于 a \bot b,如果有
h(a \times b) = h(a) \times h(b)
那就是积性函数了。
展开来写:
\sum_{d |a \times b} d \times \mu(d) = \sum_{d_1 |a} \sum_{d_2 | b} d_1 \times d_2 \times \mu(d_1) \times \mu(d_2)
对于 a \times b 的因子 d,由于 a \bot b,一定可以唯一地表示成 \gcd(d, a) \times \gcd(d, b),也就是说,左边的和号可以拆成唯一的两个数的乘积,而且这两个数一定可以在右边的和号中分别找到。
故成立。
莫比乌斯反演
考虑第一个式子:
f = 1 * g
第二个式子:
g = \mu * f
因为 \mu 是 1 的逆元(1 * \mu = e),所以乘上 1 的逆元就可以得到下面的式子了。
牛!很棒!
谢谢安哥,安哥加油!
王晨曦的朋友果然不错,牛X!
Orz