剑锋所指,心之所向。

毒瘤。

一些东西的证明放在最后的。

一些约定

高斯记号

对于命题 \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, jd 的几倍。并且交换和号。(下文和号的上界省略下取整符号)。

\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 这些函数都是积性的,所以只需要证明对于任意质数 pk \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 时,贡献为 -1i = 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

因为 \mu1 的逆元(1 * \mu = e),所以乘上 1 的逆元就可以得到下面的式子了。

已有 4 条评论

  1. 小迷弟安皮皮 小迷弟安皮皮

    牛!很棒!

    1. bwt bwt

      谢谢安哥,安哥加油!

  2. 2308229995 2308229995

    王晨曦的朋友果然不错,牛X!

  3. Orz

atcoder abc 与 CF div1 B, C 做题记录
上一篇 «
关于证明欧拉函数的积性性质
» 下一篇