OI中的数论学习笔记

素数的定义和判定

定义

如果 $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$ 为奇数，则有如下两条性质至少有一条满足：

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

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

一条都不成立。
至少一条成立。

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

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

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

扩展欧几里得定理(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)$ ，若已知 $b \cdot x' + a % b \cdot y' = g$ ，可以将式子进行如下变换：

$\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)$ 时进行计算即可。

逆元

定义与求法

如果 $\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) - 1}$ 。

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

同时，也可以通过 Exgcd 求逆元： $a \times b \equiv 1 \pmod m$ 可等价变形为 $a \times b + x \times m = 1$ ，同时， $a$ 与 $m$ 互质，也就是 $\gcd(a, m) = 1$ ，于是这就变成了 Exgcd 所讨论的问题了。计算 exgcd(a, m, b, x) ， $x$ 即为 $a \pmod 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}$

裴蜀定理

给定 $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)}$ 。

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

算法流程

设存在由 $k$ 个一元线性同余方程所组成的方程组：

$\left \{ \begin{array}{l} x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \\ \vdots \\ x \equiv b_k \pmod {m_k} \end{array} \right.$

计算所有模数的积 $M$
计算对于第 $i$ 个方程：
1. $n_i = \frac{M}{m_i}$
2. $n_i$ 在模 $m_i$ 意义下的逆元 $n_i^{-1}$
求出唯一解 $x = \sum_{i = 1}^{k}b_i \cdot n_i \cdot n_i^{-1} \pmod{M}$

大数翻倍法(补充)

假设只有两个方程：

$\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)$

则有: $g \cdot (k_1 \cdot \frac{m_1}{g} - k_2 \cdot \frac{m_2}{g}) = b_2 - b_1$

则 $g | (b_2 - b_1)$ ，设: $b_2 - b_1 = r \cdot g$

则可以得到 $k_1 m_1 - k_2 m_2 = r \cdot g$ ，使用 exgcd 求出 $k_1$ ，带入 * 式即可求出x。

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

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

BSGS算法

大小步算法，又称“北上广深算法”“阿姆斯特朗算法”“拔山盖世算法”。

数论问题：给定 $a, b, p$ ，其中 $p \leq 10^9$ 且为质数，求 $a^x \equiv b \pmod p$ 的一组解。

对于 $a^x \equiv b \pmod p$ ，一定有 $x \leq p - 1$ 。当 $x = p$ 时，根据费马小定理 $a^{p - 1} \equiv 1 \pmod p$ ，则 $a^p \equiv a^1 \pmod p$ 。

按照解的范围每 $\sqrt{p}$ 分为一组，则第一组为 $a^1, a^2, \cdots , a^{\sqrt{p}}$ ，第二组为 $a^{\sqrt{p} + 1}, a^{\sqrt{p} + 2} , \cdots , a^{2\sqrt{p}}$ ，可以注意到第二组的每个数均等于上一个数的 $a^{\sqrt{p}}$ 倍，则查看 $b$ 在第 $r, r > 1$ 组是否出现过也就等价于查看 $\frac{b}{a^{(r - 1)\sqrt{p}}}$ 使用逆元取模后，在第一组有没有出现过。

积性函数

如果函数 $f$ 满足 $gcd(a, b) = 1$ 时有 $f(ab) = f(a)f(b)$ ，则 $f$ 叫做积性函数。
如果取消互质的条件则叫做完全积性函数。

例如：

I(n) = 1, id(n) = n 这两个就是完全积性函数
欧拉函数 $\phi(n)$ ，莫比乌斯函数 $\mu$ 就是积性函数。

莫比乌斯函数：
对于 $\mu(n)$ ，先对 $n$ 分解质因数为 $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}$
则

$\mu(n) = \left \{ \begin{array}{l} 1, n = 1 \\ (-1)^r, k_1 = k_2 = \cdots = k_r \\ 0, k_t > 1 \end{array} \right.$

莫比乌斯函数接下来会经常用到。

狄利克雷卷积

定义

定义：对于两个数论函数 $f$ 和 $g$ ，这两个函数的卷积 $(f * g)(n) = \Sigma_{d | n}{f(d)g(\frac{n}{d})}$

这个定义的含义为，对两个数论函数 $f$ 和 $g$ 在 $n$ 上进行卷积，则枚举 $n$ 的每一个因子进行计算求和。

性质

交换律： $f * g = g * f$
结合律： $(f * g) * h = f * (g * h)$
分配律： $(f + g) * h = f * h + g * h$

恒等式

$\mu * I = \epsilon$ ( $\epsilon(n) = [n = 1], I(n) = 1$ ，即当 $n = 1$ 成立时， $\epsilon(n) = 1$ ，否则等于 $0$ )
$\phi * I = id$ ( $id(n) = n$ )
$\mu * id = \phi$