OI数学专题笔记 - 2

素数的定义和判定

定义

如果 $p$ 只有 1 和 $p$ 两个印子，则 $p$ 为负数。

Miller-Rabin 素性测试

如果 $n$ 为素数，取 $a < n$ ，设 $n - 1 = d \times 2^r$ ，则要么 $a^d \equiv 1 \pmod n$ ，要么 $\exists 0 \leq i < r, s.t. a^{d \times 2^i} \equiv -1 \pmod n$ 。（费马小定理的推广形式）

意思是：如果有一个素数 $n$ ，任取 $1 \leq a < n$ ，将 $n - 1$ 分解为 $n - 1 = d \times 2^r$ ，其中 $d$ 为奇数， 则有如下两条性质至少有一条满足：

1. $a^d \equiv 1 \pmod n$

2. $\exists 0 \leq i < r, s.t. a^{d \times 2^I} \equiv -1 \equiv n - 1 \pmod 1$

当任取 $1 \leq a < n$ ，可能出现以下情况：

1. 一条都不成立。

2. 至少一条成立。

若一条都不成立，则说明这个数不是素数，若至少成立一条，则说明这个数有可能是素数。

所以算法流程为：找 $k$ 个数，全部进行素性测试，若都能通过，则认为这个数是素数，若有任意一个数不通过，则这个数不是素数。

一般来说，建议选八个质数，例如 {2, 3, 5, 7, 11, 13, 17, 37}，这样的八个数可以保证算法在long long 范围内都不会出错。因为有人曾经用超级计算机枚举 long long 内的所有数进行算法检查。

逆元

定义与求法

如果 $gcd(a, m) = 1$ 且存在唯一的 $b$ 使得 $a \times b \equiv 1 \pmod m$ 且 $1 \leq b < n$ ，则 $b$ 为 $a$ 在模 $m$ 意义下的逆元。

• 费马小定理：对于任何一个质数 $p$ ，有 $a^{p - 1} \equiv 1 \pmod p$ ，其中 $1 \leq a < p$ 。因为 $a^{p - 1} \equiv 1 \pmod p$ ，所以 $a \times a^{p - 2} \equiv 1 \pmod p$ 。

• 欧拉定理：对于任意的一个数 $m$ ，有 $a^{\phi(m)} \equiv 1 \pmod m$ 。其中 $\phi(m)$ 叫做欧拉函数，表示 $1$ ~ $m$ 中有多少个数与 $m$ 互质。当 $m$ 为质数时，$\phi(m) = m - 1$ ，就变成了费马小定理。

所以，当模数 $p$ 为质数时， $a$ 的逆元为 $a^{p - 2}$ ；当模数 $m$ 为任意数时， $a$ 的逆元为 $a^{\phi(m)}$ 。

$\phi(m) = m(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_k})$ ，其中 $p_1 \cdots p_k$ 为 $m$ 的因子。

线性求逆元

如何求 $1$ ~ $n$ 所有数对质数 $p$ 的逆元?

如果对 $1$ ~ $n$ 每一个数计算它的 $p - 2$ 次方，则时间复杂度是 $O(nlogn)$ 的，有没有方法 $O(n)$ 的将它们求出来呢？

$\begin{array}{l} \forall 1 \leq i \leq n, p = ki + r \\ ki + r \equiv 0 \pmod p \\ kr^{-1} + i^{-1} \equiv 0 \pmod p \\ i^{-1} \equiv -kr^{-1} \pmod p \\ i^{-1} \equiv -kr^{-1} \pmod p \\ i^{-1} \equiv - \lfloor \frac{p}{i} \rfloor (p\ mod\ i)^{-1} \end{array}$

ExGCD

• 给定 $a, b$ ，已知 $g = gcd(a, b)$ ，求 $x, y$ ，使得 $ax + by = g$ 。

如果已知一组解 $x, y$ ，则其他解一定为 $k \cdot \frac{b}{gcd(a, b)}, -k \cdot \frac{a}{gcd(a, b)}$ 。

而 $gcd(a, b)$ 求到最后一定为 $gcd(g, 0)$ ，显然此时 $x = 1, y = 0$ 为一组解，所以现在需要将这组解向上推出两数为 $a, b$ 时的解。

因为 $gcd(a, b) = gcd(b, a$ ，若已知 $b \cdot x' + a$ ，可以将式子进行如下变换：

$\begin{array}{l} b \cdot x' + (a - b \cdot \lfloor \frac{a}{b} \rfloor) \cdot y' = g \\ a \cdot y' + (x' - \lfloor \frac{a}{b} \rfloor \cdot y') \cdot b = g \end{array}$

观察方程组

$\left \{ \begin{array}{l} a \cdot x + b \cdot y = g \\ b \cdot x' + (a - b \cdot \lfloor \frac{a}{b} \rfloor) \cdot y' = g \end{array} \right.$

则可以得到：

$\left \{ \begin{array}{l} x = y' \\ y = x' - \lfloor \frac{a}{b} \rfloor \cdot y' \end{array} \right.$

所以在计算 $gcd(a, b)$ 时进行计算即可。

裴蜀定理

给定 $a, b, c$ ，则 $ax + by = c$ 有整数解的充要条件是 $gcd(a, b) | c$ 。

中国剩余定理

目的

问题定义：给定 $N$ 个方程，形式均为 $x \equiv b_i \pmod {m_i}$ ，求 $x$ 。

这个问题问的也就是求一个 $x$ 使它满足 $x \equiv b \pmod {lcm(m_1, m_2, \cdots, m_n)}$ 。

所以中国剩余定理的用处就是求 $b$ 。

大数翻倍法

假设只有两个方程：

$\begin{array}{l} x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \end{array}$

不妨设 $m_1 \geq m_2$

令 $b_1$ 为 $b_1, b_1 + m_1, b_1 + 2m_1 ,b_1 + 3m_1 , \cdots$ ，这样得到的 $b_1$ 是显然满足第一个方程的，所以只需要逐一枚举计算 $b_1 + k \cdot m_1 \equiv b_2 \pmod {m_2}$ 即可得到 $x = b_1 + k \cdot m_1$。

则对 $n$ 个方程进行 $n - 1$ 次合并即可。

这个方法不正统，不过事实上不怎么会被卡。

ExGCD法

假设只有两个同余方程：

$\begin{array}{l} x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \end{array}$

则 $x = k_1m_1 + b_1 = k_2m_2 + b_2$

所以 $k_1m_1 - k_2m_2 = b_2 - b_1$ ，设 $g = gcd(m_1, m_2), k_1m_1 = x, k_2m_2 = y$ ，令 $b_2 - b_1 = g \cdot r$

则解出 $x', y'$ 满足 $x'm_1 + y'm_2 = g$ 再分别乘 $r$ 即可求出 $k_1, k_2$ ，带回即可求出所求的数。

且根据裴蜀定理，当同余方程有解时 $r$ 一定为整数。

对于 $n$ 个方程，则对 $n$ 个方程进行 $n - 1$ 次合并即可。