NOI 一轮复习 VIII：数学 C

本文是 NOI 一轮复习的第八篇，主要介绍了数论、线性代数、计算几何和其它数学知识。

正整数中的数论

主要是针对素数的研究。

素数与合数

如果一个数 $x(x\in\mathbb{N})$ 的约数仅有 $1$ 和它本身，那么就称 $x$ 是质数（素数），特别地，$0$ 和 $1$ 不是质数，如果一个自然数不是质数，他就是合数。

可以用线性筛在 $O(n)$ 的时间内筛出所有质数，用 $O(\sqrt{r}+(r-l+1)\log(r-l+1))$ 的时间筛出区间内的所有质数。

$p$ 进赋值序列是刻画正整数的重要方式。可以将正整数表示到 $p$ 维空间上。

大质因数

一个数最多只有一个 $\ge \sqrt{v}$ 的质数因子，这个思路非常经典。

[NOI2015] 寿司晚宴。最暴力的做法就是设 $f_{S_1,S_2}$ 代表两人选的质因数状压后分别为 $S_1,S_2$，发现 $n\le 500$，比 $19$ 大的质因数最多出现一次，可以单独记录这个大质因数，然后把每一个有这个大质因数的寿司设为一组，在这一组进行转移时另记 $g_1,g_2$ 分别代表只允许这两个人其中一个吃有这个大质因数的寿司，最后合并答案的时候还要减去最初的 $f$，因为两个人都不吃的算了两次。代码。

整除性

研究整除相关的数论。

数论分块

数论分块。$\left\lfloor\frac{n}{i}\right\rfloor$ 只有 $O(\sqrt{n})$ 中不同的取值，并且每一种取值都是一个连续的区间。

比如光速幂是利用这一点来实现的，这个技巧也可以在 $O(\sqrt{n})$ 时间内枚举到所有区间。

最经典的应用就是快速计算 $\sum_{i=1}^n f(i)g\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$，需要 $O(1)$ 计算 $\sum_{i=l}^{r}f(i)$，然后将 $g$ 相同的打包计算。

使得 $\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor$ 成立的最大满足 $i\le j\le n$ 的块的右端点为 $\left\lfloor\cfrac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$。为什么？令 $k=\lfloor\frac{n}{i}\rfloor$，可知 $k\le \frac{n}{i}$，那么 $\lfloor\frac{n}{k}\rfloor\ge i$，所以 $j=\frac{n}{i}$。时间复杂度 $O(\sqrt{n})$。

欧几里德算法

辗转相减法可以用来求解两个数的 $\gcd$：

int gcd(int a, int b) {
    if (a == b) return a; 
    if (!a || !b) return a | b; 
    if (!(a & 1)) {
        if (b & 1) return gcd(a >> 1, b); 
        return gcd(a >> 1, b >> 1) << 1; 
    }
    if (!(b & 1)) return gcd(a, b >> 1); 
    if (a > b) return gcd((a - b) >> 1, b); 
    return gcd((b - a) >> 1, a); 
}

辗转相减（除）是一个非常重要的结构，出现时往往伴随着与 $\gcd$ 相关的结论。

类欧几里德算法

万能欧几里德算法

数论函数

定义域为整数的函数是数论函数，一般我们研究数论函数中的积性函数。对于所有积性函数 $f$，都有 $f(1)=1$。

常见积性函数：

• 单位函数 $\epsilon(n)=[n=1]$，是完全积性函数。
• 常数函数 $1(n)=1$，是完全积性函数。
• 恒等函数 $\operatorname{id}_k(n)=n^k$，是完全积性函数，当 $k=1$ 时可以省略不写。
• 除数函数 $\sigma_k(n)=\sum_{d\mid n}d^k$。这样的话，$\sigma_0(n)=\tau(n)$，$\sigma_1(n)$ 代表约数和，有 $\sigma_k(n)=\prod_{i=1}^s\left(\sum_{j=0}^{\alpha_i}p_i^{jk}\right)=\prod_{i=1}^s\sigma_k(p_i^{\alpha_i})$。
• 欧拉函数，$\varphi(n)$ 代表 $1\sim n$ 中与 $n$ 互质的数的个数。
• 本质不同质因子个数函数 $\omega(n)=\sum_{p}[p\mid n]$。

线性筛可以计算所有的积性函数（前提是可以快速求出 $f(p^{k+1})$，只需要记录 $low$ 代表最小质因子的最高次幂：

for (int i = 2; i <= n; i++) {
    if (!vis[i]) prime[++tot] = i, f[i] = ..., low[i] = i;  // 单独算 f(p)
    for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
        vis[i * prime[j]] = 1;
        if (i % prime[j] == 0) {  // i 与 p 不互质
            low[i * prime[j]] = low[i] * prime[j];
            if (i == low[i]) f[i * prime[j]] = ...;  // i = p^k，单独算 f(p^{k+1})
            else f[i * prime[j]] = f[i / low[i]] * f[low[i] * prime[j]]; 
            break; 
        }
        low[i * prime[j]] = prime[j]; 
        f[i * prime[j]] = f[i] * f[prime[j]];  // i 与 p 互质，f(ip) = f(i)f(p)
    }
}

狄利克雷卷积是数论函数的基本运算。定义：

$$h(n)=\sum_{d\mid n}f(d)g\left(\frac{n}{d}\right)$$

简记为 $h=f*g$。

狄利克雷卷积具有交换律、结合律和分配律。

首先，$\epsilon*f=f$。因此单位函数 $\epsilon$ 为狄利克雷卷积的单位元，那么就可以定义数论函数的逆元 $f^{-1}$，满足 $f*f^{-1}=\epsilon$。

一个 $f$ 存在逆元，当且仅当 $f(1)\ne 0$，并且逆元唯一。$f=g$ 的充要条件是 $f*h=g*h(h(1)\ne 1)$。这样一来有 $g(n) = -\cfrac{\sum\limits_{d \mid n, d \neq n} g(d)f\left(\dfrac n d\right)} {f(1)}$。

积性函数的狄利克雷卷积是积性函数，积性函数的逆元也是积性函数。

以下是一些常用的狄利克雷卷积：

• $1*1=\tau$，
• $\varphi *1=\operatorname{id}$。

任意数论函数 $f$ 卷常数函数 $1$ 等价于做 $f$ 的狄利克雷前缀和，即：$g=f*1,g(n)=\sum_{d\mid n}f(d)$。含义是对每个 $n$ 计算给定数论函数在其所因数处的取值和。

将每个数写成无穷序列 $a_n=\{c_1,c_2,\cdots\}$ 表示 $n=\prod p_i^{c_i}$。由于 $x\mid y$ 的充要条件为 $a_x(c_i)\le a_y(c_i)$，因此 $f*1$ 可以看成对下标做其无穷序列的高维前缀和。

模板，这里是对 $a$ 做狄利克雷前缀和，本质上是分组背包，每个质数是一组，每组的体积是 $p^k$，代码。

欧拉函数

欧拉函数，即 $\varphi(n)$，代表 $1\sim n$ 中与 $n$ 互质的数的个数。

设 $n=\prod p_i^{k_i}$，则有：

$$\varphi(n)=n\prod(1-\cfrac{1}{p_i})=n\prod \cfrac{p_i-1}{p_i}$$

欧拉反演：$n = \sum_{d\mid n} \varphi(d)$。

莫比乌斯函数

我们定义莫比乌斯函数：

$$\mu(n)=\begin{cases}1,&n=1,\\0,&\exists d>1,d^{2}\mid n, \\(-1)^{\omega(n)},&\mathrm{otherwise}. \end{cases}$$

实际上它是在对 $\mathbb{N}$ 做容斥。设 $g(n)=\sum_{n\mid d} f(d)$，已知 $g$，要求 $f(1)$。$f(1)$ 等于 $g$ 在 $1$ 的倍数处取的取值和，减去质数处的取值和，但是多减了两个质数乘积的地方，因此还要加回来。这就是容斥原理，容斥系数是 $(-1)^{\omega(n)}$。

它不仅是积性函数，还满足：

$$\sum_{d\mid n}\mu(d)=\begin{cases} 1,&n=1,\\ 0,&n\neq 1. \end{cases}$$

上述式子描述的其实是 $\mu*1=\epsilon$，也就是说 $\mu$ 是 $1$ 的逆元。这是莫比乌斯函数最重要的性质，其引出了性质：$\sum_{d\mid n}\mu(d)=[n=1]$，我们可以将这个艾弗森括号转化为和式，这样更加方便计算。两者的转化称之为莫比乌斯反演。

莫比乌斯反演有以下结论：

• 若 $g=f*1$，则 $f=g*\mu$。
• 若 $g(n)=\sum_{n\mid d}f(d)$，则 $f(n)=\sum_{n\mid d} \mu\left(\dfrac d n\right) g(d)$。这也被称为莫比乌斯变换，实际上就是把上面那一条给写出来。
• 由于 $\varphi * 1 = \operatorname{id}$，因此 $\operatorname{id} * \mu =\varphi$。

一个常见的应用是，$[\gcd(i,j)=1]=\sum_{d\mid \gcd(i,j)}\mu(d)$。虽然看起来这像是废话，但这一步将 $i,j$ 互质转化为了枚举 $\gcd(i,j)$ 的约数 $d$。如果 $i,j$ 同样需要枚举，那么枚举 $d$ 并计算合法的 $i,j$ 个数（当且仅当 $d\mid i,d\mid j$）即可。具体来说：

$$\begin{aligned} \sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m [\gcd(i, j) = 1] & = \sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m \sum\limits_{d\mid \gcd(i, j)} \mu(d) \\ & = \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m [d\mid i\land d\mid j] \\ & = \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \left\lfloor \dfrac n d \right\rfloor \left\lfloor \dfrac m d \right\rfloor \\ \end{aligned}$$

就可以直接使用数论分块在 $O(\sqrt{n}+\sqrt{m})$ 的时间内计算。

杜教筛

我们要求积性函数 $f$ 的前缀和，设 $S(n)=\sum_{i=1}^{n}f_i$，再找一个积性函数 $g$，考虑它们的狄利克雷卷积的前缀和：

$$\begin{aligned} &\sum_{i=1}^{n} \sum_{d\mid i} f(d)g\left(\frac i d\right)\\ =&\sum_{d=1}^n g(d)\sum_{i=1}^{\left\lfloor\frac n d\right\rfloor} f(i)\\ =&\sum_{d=1}^n g(d)S\left(\left\lfloor\frac n d\right\rfloor\right) \end{aligned}$$

而我们有：

$$\begin{aligned} g(1)S(n)&=\sum \limits _{i=1}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor) - \sum \limits _{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)\\ &=\sum\limits_{i=1}^{n}(f*g)(i) - \sum \limits _{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor) \end{aligned}$$

时间复杂度为 $O(n^{\frac 3 4})$，我们先线性筛出前 $m$ 个的答案，那么 $m=n^{\frac 2 3}$ 时，时间复杂度为 $O(n^{\frac 2 3})$。

模板。有 $\mu * 1 =\epsilon,\varphi * 1 =\operatorname{id}$，那么直接杜教筛即可。代码。

Min_25 筛

例题

巩固一些基础内容。

[CF1656H] Equal LCM Subsets

Portal.

从质因数幂次的角度考虑，思考哪些是集合中不能要的地雷。

如果 $a_i$ 不能留在集合中，那么它至少有一个质因子的幂次比 $b$ 中其它所有数都大。也就是说，如果 $\gcd \cfrac{a_i}{\gcd(a_i,b_j)}>1$，那么 $a_i$ 就该被从集合中删除。相当于单点修改，查询全局 $\gcd$，这个过程只能进行 $O(n+m)$ 轮，线段树直接维护，每轮修改是 $O((n+m)\log (n + m))$ 的，可以接受。代码。

* [Luogu P5435] 基于值域预处理的快速 GCD

Portal.

模意义下的数论

尽管数论相关的题目似乎已经退出环境，但是本身还是比较有意思的。

拉格朗日定理：在模 $p$ 意义下，最高次项系数非 $0$ 的 $n$ 次多项式至多有 $n$ 个根。

线性同余方程组

可以使用 CRT 解决模数互质的情况，exCRT 解决模数不互质的情况。

$$\begin{cases} x\equiv a_1 \pmod {m_1}\\ x\equiv a_2 \pmod {m_2}\\ \cdots\\ x\equiv a_3 \pmod {m_3}\\ \end{cases}$$

模数互质

设 $M=\prod_{i=1}^{n}m_i,M_i=m\div m_i$，$t_i$ 是线性同余方程 $M_it_i\equiv 1 \pmod{m_i}$ 的一个解，也就是说 $t_i$ 是 $M_i$ 模 $m_i$ 的逆元（显然 $M_i \perp m_i$ 当且仅当 $m_i$ 两两互质），那么 $x=\sum_{i=1}^{n}a_iM_it_i + kM$，最小非负整数解需要求 $\sum_{i=1}^{n}a_iM_it_i\bmod M$。

i64 CRT(void) {
    // x === a[i] (mod m[i])
    i64 ans = 0, x;
    for (int i = 1; i <= n; ++i) {
        M[i] = mm / m[i]; 
        t[i] = inv(M[i], m[i]); 
        ans = (ans + a[i] * M[i] * t[i]) % mm;
    }
    return (ans % mm + mm) % mm; 
}

模数不互质

考虑如何合并两个方程组。我们先假定一定可以合并，然后看看什么时候合并之后的解是 $\varnothing$。

这玩意儿等价于 $a=k_1m_1+r_1=k_2m_2+r_2 \Longrightarrow k_1m_1-k_2m_2=r_2-r_1$。这个熟悉！二元一次不定方程！直接使用 exgcd 计算即可。

于是：

• 如果 $\gcd(m_1,m_2)\mid (r_2-r_1)$，那么可以合并；
• 否则，exCRT 是无解的。

现在有引理：合并之后的模数是原来两个模数的 lcm。

具体来说，设当前合并的余数为 $M$，当前答案为 $ans$，那么任意一个 $ans+Mx$ 都满足答案，我们需要找到一个最小的 $x$ 使得 $ans+Mx\equiv a_i\pmod {m_i}$，可以使用扩展欧几里得来解决。

i64 exCRT(void) {
    // x === A (mod B)
    i64 M = 1, ans = 0; // M 为当前合并的模数，ans 为当前答案
    for (int i = 1; i <= n; ++i) {
        i64 b = B[i], x, y, c = (A[i] - ans + b) % b;
        i64 g = exgcd(M, b, x, y); // Mx + by = gcd(M, b)
        if (c % g != 0) return -1;
        x = (__int128)x * (c / g) % (b / g);
        ans = ans + M * x;
        M = b / g * M;
        ans %= M; 
    }
    return (ans % M + M) % M;
}

如果模数不是质数，那么可以使用 exCRT 合并。

阶与原根

例题

巩固一些基础内容。

[CF1848E] Vika and Stone Skipping

Portal.

如果跳 $g$ 次，需要满足：

$$2x\prod X_i=(2f-g+1)g$$

求的就是 $2x\prod X_i$ 的奇因数个数。提前将 $x$ 除掉其 $\operatorname{lowbit}$ 即可直接统计其因数。

直接维护即可。注意模数过小时逆元的爆炸问题。代码。

[NOI2018] 屠龙勇士

Portal.

由于我们选择的武器是固定的，所以实际上依然是 exCRT，只不过方程换成了 $bx\equiv a\pmod p$。这样是一样的，设当前合并的模数为 $M$，答案为 $ans$，那么下一个合并要满足 $b(ans+Mx)\equiv a\pmod p$，也就是 $bMx-py=a-b\times ans$。

注意一个细节：解出来的解必须能将龙打掉，也就是能将血打成小于等于 $0$，否则即使满足同余方程也没用。记录一个能把血量打成负数的最小攻击次数，然后如果答案小于这个攻击次数，答案就加上还需要打的次数。代码。

[CF338D] GCD Table

Portal.

首先如果有解，那么那个 $x$ 应该满足 $\operatorname{lcm}(a_1,a_2,\cdots,a_k) \mid x$。实际上 $x$ 就应该等于 $\operatorname{lcm}$，因为如果增加倍数，$y$ 的构造只会变得更加困难。

这样我们只需要满足 $a_i\mid y+i-1$，exCRT 求一下即可。代码。

线性代数

概念

高斯消元法

我们可以使用高斯消元以 $O(n^3)$ 的时间求解方程组的解。具体来说就是一个一个地加减消元，转化成上三角形式，然后再代入即可。

线性基

对于异或线性基，我们使用贪心法构建：

void insert(i64 x) {
    for (int i = 50; i >= 0; --i)
        if (x & (1ll << i)) {
            if (!p[i]) { p[i] = x; ++cnt; break; }
            else x ^= p[i];
        }
}

i64 askmx(void) {
    i64 ans = 0;
    for (int i = 50; i >= 0; --i)
        if ((ans ^ p[i]) > ans) ans ^= p[i];
    return ans;
}

最小异或值是 $\min\{p_i\}$。

线性基的合并直接暴力合并即可。

LGV 引理

对于一个 DAG，

简单计算几何

数学杂项

连分数

群论入门

博弈论

博弈论主要研究一些有竞争或对抗性质的对象，在一定规则下/产生的各种行为。

对于公平组合游戏，我们通常会选择计算 SG 函数；对于非公平游戏，我们会选择推导一些性质。

概念

我们从 Nim 游戏开始研究。有 $n$ 堆石子，每人每次可从任意一堆石子里取出正整数枚石子扔掉，谁不能动谁就输了。

我们将每个状态视作一个节点，那么博弈情况就可以刻画成一张有向图。不难发现，异或和为 $0$ 时先手必败。

大部分的公平组合游戏（所有玩家都可以操作对方能操作的东西）都可以转换为有向图游戏，对于状态 $x$ 和它的 $k$ 个后继状态 $y_1,\cdots,y_k$，定义 SG 函数为：

$$\operatorname{SG}(x)=\operatorname{mex}\{\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k)\}$$

对于由 $n$ 个有向图游戏组成的组合游戏，当且仅当 $\oplus \operatorname{SG}(s)\ne 0$ 的时候，先手必胜，称之为 P 态。也就是说，$\operatorname{SG}(x)=0$ 是必败态，称之为 N 态。

SG 定理：一个游戏的 SG 值是其所有子游戏的 SG 值的异或和，这可以说明 Nim 游戏结论的由来。

[HNOI2007] 分裂游戏。终止状态是所有豆子在 $n$ 号瓶子，而每个豆子是独立的，直接暴力 DP 即可。代码。

Anti-SG 定理

如果不能动的人获胜，那么这个游戏叫做反常游戏。同样的，有判断必胜条件的 Anti-SG 定理：

1. 如果游戏的 SG 值为 $0$，那么所有子游戏的 SG 值都不超过 $1$ 时先手必胜（还是要异或值为 $0$）；
2. 如果游戏的 SG 值不是 $0$，那么至少有一个子游戏的 SG 值超过 $1$ 时先手必胜。其在决策过程中可以转化为上述情况。

模板。

经典博弈模型

博弈论中有一些特别经典的问题，我们来介绍一些。

威佐夫博弈

我们可以发现以下状态是先手必败的：

• $(0, 0)$，
• $(1, 2)$，
• $(3, 5)$，
• $(4, 7)$，
• $(6, 10)$，
• $(8, 13)$。

两者的差是自然数列，第一个数是之前所有新出现的数是之前出现数的 mex。可以证明结论是 $a=\left\lfloor (b-a)\times \cfrac{\sqrt{5}+1}{2}\right\rfloor$ 时先手必败。

公平组合

博弈论除了 SG 定理外，剩下的内容几乎全部基于 DP。有时候通过打表来寻找 SG 函数的规律也是一个不错的选择。

[CF768E] Game of Stones

Portal.

可以考虑一个石堆会被取多少次，发现是从 $1$ 开始依次取，然后就转成了正常的 Nim 游戏。代码。

[HNOI2014] 江南乐

Portal.

考虑枚举所有的 $m$，那么可以计算所有 $n$ 的 SG 值。发现整除分块可以优化枚举 $m$ 这个过程，因为 $n/m$ 和 $n/m+1$ 必有一个奇偶性不变。代码。

[AGC017D] Game on Tree

Portal.

问题可以分解成若干棵子树，每棵子树都带着根节点，然后发现其 SG 值是子树的 SG 值加 $1$，直接处理即可。代码。

[AGC010D] Decrementing

Portal.

如果初始 $\sum a_i-1$ 为奇数，那么先手可以一直维持这个状态（只需要操作偶数即可，情况不会改变）。

初始为偶数呢？如果局面下只有一个奇数，那么操作它就可以出现偶公因数，模拟即可。代码。

[AGC016F] Games on DAG

Portal.

不难想到按照 SG 值进行分层转移，对于新增加的 SG 值更小的部分，一定要有边连向它们中的点来保证 SG 值的大小。转移的时候直接枚举子集 $S$，判断到达的 SG 值更小的集合 $T$，此时令 $\operatorname{SG}(T)=k$，设 $f_i$ 代表考虑集合 $i$ 中的点时 $\operatorname{SG}(1)=\operatorname{SG}(2)$ 的方案数，转移：

• 对于 $T\rightarrow S$ 的边，每一个 $T$ 中的元素都至少向 $S$ 中连一条边；
• 对于 $S\rightarrow T$ 的边，随便连即可。

直接做即可。代码。

[ABC278G] Generalized Subtraction Game

Portal.

如果可以先手第一步下在中间，然后我们就下模仿棋就行了。

否则，此时选择的区间长度固定，考虑计算 SG 函数，令 $\operatorname{SG}_i$ 代表长度为 $i$ 的游戏的 SG 值。

对于 $i<l$，有 $\operatorname{SG}_i=0$，否则枚举选择的长度，有 $\operatorname{SG}_i=\operatorname{mex}_{j=0}^{i-l}\{\operatorname{SG}_{j} \operatorname{xor} \operatorname{SG}_{i-j-l}\}$。

输出方案时采用 set 维护连续段，不断选择后手必败的区间即可。

[CF1458E] Nim Shortcuts

Portal.

正常情况下，黑色的是先手必败的：

但如果存在限制（黄色的也是必败态，那么情况会发生改变）：

可以发现必败态是若干条斜线，初始斜线是 $x=y$，特殊点会导致斜线向下和向右平移，发现这是个二维数点，扫描线维护使其向 $x$ 轴方向平移的个数，树状数组维护 $y$ 轴方向，用 $x-y$ 的值判断是否在斜线上即可。代码。

非公平组合

比较有趣。

[AGC048D] Pocky Game

Portal.

设 $f_{l,r}$ 代表 $a_l$ 至少为多少才能使得 $[l,r]$ 先手必胜，$g_{l,r}$ 代表 $a_r$ 至少为多少才能使得 $[l,r]$ 后手必胜。转移时由于最后是一个一个取，直接算即可，代码。

[CF1033G] Chip Game

Portal.

模 $a+b$ 意义下的局面是等价的，考虑枚举 $a+b$，将 $v$ 排序，计算出合法的值域 $[v_{i-1}+1,v_i]$，而且应该减去存在两个 $2a\le v_i$ 的情况，随便算算就好了。代码。

题车