一些基础数论知识

## 1 欧几里德算法 ### 1.1 $\gcd (a, b) = \gcd(b, a \bmod b)$ 记 $a = k \cdot b + r$ ，满足 $a, b, k, r \ge 0,r < b$ ，$r = a - k \cdot b$ 。 设 $\gcd (a,b) = d$ ，则有 $(k \cdot b)| d $, $a | d \Rightarrow r|d \Rightarrow \gcd(a,b) = \gcd(b, a \bmod b)$ 。 注意到每两次迭代 $a$ 必然减少至少一半，迭代下去即可在 $O(\log w)$ 的时间内求出两数最大公约数。 ### 1.2 $ax + by = c$ 的整数解 #### 1.2.1 裴蜀定理 > 裴蜀定理: 若 $a,b$ 是整数,且 $\gcd(a,b)=d$ ，那么对于任意的整数 $x,y$ ，$ax+by$ 都一定是 $d$ 的倍数。特别地，一定存在整数 $x,y$ ，使 $ax+by=d$ 成立。 当 $c \nmid \gcd(a,b)$ ，方程无解，否则方程有无穷多组解。 假设我们求得 $x_0, y_0$ 满足 $\displaystyle a \cdot x_0 + b \cdot y_0 = \gcd(a,b) \Rightarrow a \cdot \frac{c \cdot x_0}{\gcd(a,b)} + b \cdot \frac{c \cdot y_0}{\gcd(a,b)} = c$ ，我们可以通过如下方法构造方程通解: $$ x = \frac{c \cdot x_0}{\gcd(a,b)} + \frac{b}{\gcd(a,b)} \cdot k, y = \frac{c \cdot y_0}{\gcd(a,b)} - \frac{a}{\gcd(a,b)} \cdot k, k \in Z $$ 接下来我们考虑如何求得满足上述条件的 $x_0, y_0$ 。 #### 1.2.2 扩展欧几里德算法 (ex-GCD) $$\begin{aligned} a \cdot x_0 + b \cdot y_0 &= \gcd(a,b) \\ \ b \cdot x_0' + (a - \lfloor \frac{a}{b} \rfloor \cdot b) \cdot y_0' &= \gcd(b, a \bmod b)\\ \gcd(a,b) &= \gcd(b, a\bmod b)\\ \Rightarrow b \cdot x_0' + a \cdot y_0' - \lfloor \frac{a}{b} \rfloor \cdot b \cdot y_0' &= \gcd(b, a \bmod b)\\\Rightarrow b \cdot (x0' - \lfloor \frac{a}{b} \rfloor \cdot y_0') + a \cdot y_0' &= \gcd(b, a \bmod b)\\ \Rightarrow y_0 &= x_0' - \lfloor \frac{a}{b} \rfloor \cdot y_0',x_0 = y_0' \end{aligned} $$ 这样我们求出一组满足特解 $x_0, y_0$ 。 #### 1.2.3 例题 给定 $n$ 个数 $a_i$，对每个数可以选或不选，即有 $2^n$ 种选择方式。 $Q$ 次询问，每次询问给定 $w_j$ ,求有多少种选择方式，满足方程 $$\displaystyle \sum_{i = 1}^k x_ia_i \equiv w_j \mod{P}$$ 有解 ，这里 $k$ 为选择的数的集合大小。 $n, q \leq 10^6, P \leq 10^9$ (Source HAOI2018) 方程有解得条件是 $\gcd(a_1, a_2, …, a_k, P) \mid w_j$ 设 $F[i][j]$ 表示前 $i$ 个数，选择的数和 $P\gcd$ 为 $j$ 的方案数，转移分这个数选不选讨论即可。 $O(n \sigma_0(P))$ 将和 $\gcd(a_i,P)$ 相同的数放在一起转移。 $O(\sigma_0^2(P))$ 。 ## 2 线性同余方程组 ### 2.1 同余方程 求关于 $x$ 的同余方程 $ax \equiv b \mod m$ 的最小正整数解。 同余方程可以改写为 $ax = my + b$ 使用扩展欧几里德算法求解即可。 一次同余方程 $ax \equiv b \mod m$ 解的个数为 $\gcd(a,m)$ 。 ### 2.2 同余方程组 #### 2.2.1 两个方程的情况 合并方程 $$ \begin{aligned} x \equiv y \mod m_1\\ x \equiv y \mod m_2 \end{aligned} $$ 做法大致如下： $m_1 | (x - y), m_2 | (x - y) \Rightarrow \mathrm{lcm} (m_1, m_2) | (x - y) \Rightarrow x \equiv y \mod \mathrm{lcm}(m_1,m_2)$ 。 #### 2.2.2 $k$ 个方程，模数两两互质(CRT) 合并方程 $$ \begin{cases} x \equiv y_1 & \mod m_1 \\ x \equiv y_2 &\mod m_2 \\ & \cdots\\ x \equiv y_{k-1} &\mod m_{k-1} \\ x \equiv y_k &\mod m_k \end{cases} $$ 满足 $\forall m_i,m_j,\gcd(m_i, m_j) =1\ (m_i \neq m_j)$ 。 > 中国剩余定理: 在满足 $\gcd(m_i, m_j) =1\ (m_i \neq m_j) $ 的条件下，$x$ 在模 $\prod_{i = 1}^k m_i$ 意义下是存在且唯一的。 这组解是这样的： $$ \begin{aligned} x \equiv \sum_{i = 1}^k M_i \cdot y_i \cdot M_i^{-1} \mod M \\ M = \prod_{i = 1}^k m_i, M_i = \frac{M}{m_i} \end{aligned} $$ $M_i^{-1}$ 是 $M_i$ 在模 $m_i$ 意义下的逆元。 具体可以这么理解: $$\begin{aligned} (1) \begin{cases} x_{1} \equiv 1 & \mod m_1\\ x_{1} \equiv 0 & \mod m_2\\ & \cdots\\ x_{1} \equiv 0 & \mod m_{k-1}\\ x_{1} \equiv 0 & \mod m_k \\ \end{cases}(2) \begin{cases} x_{2} \equiv 0 & \mod m_1 \\ x_{2} \equiv 1 & \mod m_2 \\ x_{2} \equiv 0 & \mod m_3 \\ & \cdots \\ x_{2} \equiv 0 & \mod m_{k-1}\\ x_{2} \equiv 0 & \mod m_k \\ \end{cases} \\ \cdots \\(k-1) \begin{cases}x_{k-1} \equiv 0 & \mod m_1\\ x_{k-1} \equiv 0 & \mod m_2 \\ & \cdots\\x_{k-1} \equiv 0 &\mod m_{k-2}\\x_{k-1} \equiv 1 &\mod m_{k-1}\\ x_{k-1} \equiv 0 &\mod m_k \\ \end{cases} (k)\begin{cases}x_k \equiv 0 & \mod m_1 \\x_k \equiv 0 & \mod m_2 \\ & \cdots\\ x_k \equiv 0 &\mod m_{k-1} \\ x_k \equiv 1 &\mod m_k \\ \end{cases}\end{aligned} $$ 每个方程可以化为 $$\begin{cases} x_i \equiv 0 & \mod M_i\\x_i \equiv 1 & \mod m_i\\ \end{cases} $$ 当 $\displaystyle x_i = M_i \cdot M_i^{-1}$ 时，方程成立，$\displaystyle \sum_{i = 1}^k x_i \cdot y_i \mod M$ 即为一个可行解。 #### 2.2.3 $k$ 个方程，模数两两不一定互质 (ex-CRT) 合并方程 $$ \begin{cases} x \equiv y_1 & \mod m_1 \\ x \equiv y_2 & \mod m_2 \\& \cdots\\ x \equiv y_{k-1} &\mod m_{k-1} \\ x \equiv y_k &\mod m_k \end{cases} $$ 注意这里不保证模数互质。 对于 $$ \begin{cases} x \equiv y_1 & \mod m_1 \\ x \equiv y_2 & \mod m_2 \\ \end{cases}$$ 两个方程可以写成 $$\begin{cases}x = y_1 + m_1 \cdot x'\\x = y_2 + m_2 \cdot y'\end{cases}$$ 因此有 $y_1 + m_1 \cdot x'=y_2 + m_2 \cdot y'$ ，即 $m_1 \cdot x' + m_2 \cdot y' = (y_2 - y_1)$ 我们解出 $x_0, y_0$ 满足 $m_1 \cdot x0 + m_2 \cdot y_0 = \gcd(m_1,m_2)$ 且 $x_0$ 为最小正整数。 因此有: $\displaystyle x' = \frac{(y_2 - y_1) \cdot x_0}{\gcd(m_1, m_2)} + \frac{m_2}{\gcd(m1,m2)} \cdot k$ 。 带入 $x$ 有: $\displaystyle x = y_1 + m_1 \cdot x' = y_1 + m_1 \cdot \frac{(y_2 - y_1) \cdot x_0}{\gcd(m_1, m_2)} + \mathrm{lcm}(m_1,m_2) \cdot k$ 两边对 $\mathrm{lcm}$ 取模，有: $\displaystyle x \equiv y_1 + m_1 \cdot \frac{(y_2 - y_1) \cdot x_0}{\gcd(m_1, m_2)} \mod \mathrm{lcm} (m_1,m_2)$ 这样我们将两个方程合并为一个新方程。 顺次做下去即可。 #### 2.2.4 方程组系数 $\neq 1$ (NOI2018屠龙勇士) 合并方程 $$ \begin{cases}a_1 \cdot x \equiv y_1 & \mod m_1 \\ a_2 \cdot x \equiv y_2 &\mod m_2 \\ & \cdots\\ a_{k-1} \cdot x \equiv y_{k-1} & \mod m_{k-1}\\a_k \cdot x \equiv y_k &\mod m_k \end{cases} $$ 只需要将方程化为 2.2.3 中的形式即可。 $a_i \cdot x \equiv y_i \mod m_i \Leftrightarrow a_i \cdot x + m_i \cdot y = y_i$ 若 $ \gcd(a_i,m_i)\nmid y_i$ 显然无解，否则可以解出一组 $x_0,y_0$ 满足 $a_i \cdot x_0 + m_i \cdot y_0 = \gcd(a_i,m_i)$ 且 $x_0$ 为最小自然数。 根据1.2.1有 $\displaystyle a_i \cdot \frac{y_i \cdot x_0}{\gcd(a_i, m_i)} + m_i \cdot \frac{y_i \cdot y_0}{\gcd(a_i,m_i)} = y_i$ ， $\displaystyle x = \frac{y_i \cdot x_0}{\gcd(a_i, m_i)} + k \cdot \frac{m_i}{\gcd(a_i,m_i)}$ 。 即 $\displaystyle x \equiv \frac{y_i \cdot x_0}{\gcd(a_i, m_i)} \mod \frac{m_i}{\gcd(a_i,m_i)} $ 这样问题就转换成2.2.3的问题了。 ### 2.3 例题 交互题。给定一个长度为 $n$ 的串，这个串是加密后的，加密的方式是交换至多 $n-1$ 次任意两个位置的字符。你可以询问交互库至多 $3$ 次，每次输入给交互库一个长度为 $n$ 的串，交互库返回加密后的结果。现在询问加密前的串是什么。 $n \leq 10^4$, 给定的串的每一位均为小写字母，且输入给交互库的串的每一位也必须是小写字母。 (Source CF EduRound60) 第一次 可以询问 $(abc\dots w)(abc\dots w)\dots $ 第二次 可以询问 $(abc \dots y)(abc \dots y)\dots $ 第三次 可以询问 $(abc \dots z)(abc \dots z) \dots $ 每次可以得到一个位置 $\mod 23, 25, 26$ 的结果，CRT回去即可。 $23 * 25 * 26 > 10^4$，因此解可以唯一确定。 ## 3 总结 本文从基础的欧几里得算法、扩展欧几里得算法出发，自然导入了同余方程问题，通过介绍中国剩余定理，并进而介绍了这一问题更一般形式以及解法。 **希望这篇美妙的文章，可以给即将参加省队选拔赛的你，提供一个有力的援助。** **点赞在右下角**