一些基础数论知识

2018-09-05 02:19:42


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 总结

本文从基础的欧几里得算法、扩展欧几里得算法出发,自然导入了同余方程问题,通过介绍中国剩余定理,并进而介绍了这一问题更一般形式以及解法。

希望这篇美妙的文章,可以给即将参加省队选拔赛的你,提供一个有力的援助。

点赞在右下角