记录一些结论作为备忘可以时常翻翻。
模意义下的数和运算
模相关简单运算
对于整数 $a, b$,满足 $b \gt 0$,那么存在唯一的整数 $q, r$,满足 $a = bq + r$,其中 $0 \leq r \lt b$。在这之中,我们称 $q$ 为商、$r$ 为余数。
余数使用 $a \bmod b$ 或者 $a % b$ 表示
一下是一些常见的有关模的运算:
- $(a + b) \bmod M = (a \bmod M + b \bmod M) \bmod M$
- $(a - b) \bmod M = (a \bmod M - b \bmod M) \bmod M$
- $(a \times b) \bmod M = (a \bmod M \times b \bmod M) \bmod M$
注意到除法并不适用,下文会引出乘法逆元解决模意义下的除法运算。
同余
如果两数 $x, y$ 除以 $b$ 的余数相等,那么称 $x, y$ 模 $b$ 同余,记作 $x \equiv y (\bmod b)$。
以下性质显然:
- 反身性:$x \equiv x (\bmod M)$
- 对称性:$x \equiv y (\bmod M)$,则 $y \equiv x (\bmod M)$
- 传递性:$x \equiv y (\bmod M), y \equiv z (\bmod M)$,则 $x \equiv z (\bmod M)$
根据我们刚刚提到的模意义下的运算规律,还可以得到以下性质:
- 同加性:若 $x \equiv y (\bmod M)$,则 $x + z \equiv y + z (\bmod M)$
- 同乘性:若 $x \equiv y (\bmod M)$,则 $x \times z \equiv y \times z (\bmod M)$
- 同幂性:若 $x \equiv y (\bmod M)$,则 $x^n \equiv y^n (\bmod M)$
下面这条性质非常重要:
$$x \equiv y (\bmod b) \Leftrightarrow b | (x - y)$$同余方程和裴蜀定理
裴蜀定理
在 OI 中,形如 $ax + by = c$ 的二元一次不定方程只需要解决 $a, b, c$ 都是整数的情况。
对于整数 $a, b$,设他们的最大公约数 $\gcd(a, b) = d$,一定存在一组整数 $(x, y)$ 使得 $ax + by = d$。
对于整数 $a, b, c$,$ax + by = c$ 有整数解当且仅当 $\gcd(a, b) \lvert c$。
扩展欧几里得算法
欧几里得算法求 $a, b$ 最大值的过程:
- 当 $b = 0$ 时,$a, b$ 的最大公约数就是 $a$
- 求出 $b, a \bmod b$ 的最大公约数,设为 $g_0$
- 令 $g = g_0$,$g$ 就是 $a, b$ 的最大公约数
仿照欧几里得算法求解不定方程的过程:
- 当 $b = 0$ 时,$ax + by = d$ 的解是 $x = \dfrac{d}{a}$,$\forall y$。
- 求出 $bx + (a \bmod b)y = d$ 的一组解,设为 $(x_0, y_0)$。
- 令 $(x, y) = f((x_0, y_0))$,$(x, y)$ 就是 $a_x + b_y = d$ 的一组解。其中 $f((a, b))$ 指将 $(a, b)$ 这一对数进行变换。
变化如下:令 $(x, y) = (y_0, x_0 - \lfloor \dfrac{a}{b} \rfloor y_0)$。
可以发现,设 $a_x + b_y = d = k \times \gcd(a, b)$,那么每次迭代的得到的解都是在求解 $ax + by = \gcd(a, b)$ 时得到的解的 $k$ 倍,所以不管 $d$ 取多少,最后的迭代中取 $x = k, y = 0$ 是没有问题的。
C++ Template:
<template typename T>
T exgcd(T a, T b, T &x, T &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
T d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
乘法逆元
若 $ax \equiv 1 (\bmod p)$,则称 $x$ 为 $a$ 在模 $p$ 意义下的乘法逆元,记为 $a^{-1} (\bmod p)$
注意,在 $[0, p)$ 这一范围内,模 $p$ 的逆元(若存在)是唯一的。
求解乘法逆元的方法有两种:
扩欧求解乘法逆元
容易发现乘法逆元的定义式和 $\exists y, ax + py = 1$ 等价。这也就是一个关于 $a, p$ 的不定方程,使用扩欧解决,又裴蜀定理易得,存在 $a$ 在模 $p$ 意义下的逆元当且仅当 $\gcd(a, p) = 1, a \bot b$。
C++ Template:
<template typename T>
T exgcd(T a, T b, T &x, T &y) {
// 参见上文
...
}
T inv(int a, int p) {
int x, y;
exgcd(a, p, x, y);
return x;
}
费马小定理求解乘法逆元
费马小定理定义如下:
若 $\forall p \in \mathbb{P}$,且 $a$ 不是 $p$ 的倍数,则 $a^{p - 1} \equiv 1 (\bmod p)$。
假设 $p$ 是质数,可知如果 $a$ 不是 $p$ 的倍数,有 $a \times a^{p - 2} = a^{p - 1} \equiv 1 (\bmod p)$。所以 $a$ 在模 $p$ 意义下的乘法逆元就是 $a^{p - 2}$,可以使用快速幂解决。
C++ Template:
<template typename T>
T expow(T a, T b, const T p) {
T res = 1;
for (; b; b >>= 1) {
if (b & 1)
res = 1ll * res * a % p;
a = 1ll * a * a % p;
}
return res;
}
T inv(T a, T p) {
return expow(a, p - 2, p);
}
同余方程与中国剩余定理
中国剩余定理
一般而言,中国剩余定理用来解决这样的一类同余方程组:
$$ \begin{cases} x \equiv a_1 (\bmod m_1) \\ x \equiv a_2 (\bmod m_2) \\ \vdots \\ x \equiv a_n (\bmod m_n) \end{cases} $$其中,$m_1, m_2, \dots, m_n$ 两两互质,则对于任意整数 $a_1, a_2, \dots, a_n$,上面这个方程组有解。
解决方法如下:
- 设 $M = \prod^{n}_{i = 1} m_i$
- 设 $M_i = \dfrac{M}{m_i}$
- 设 $t_i = M^{-1}_i$ 为 $M_i \bmod m_i$ 的逆元(因为 $M_i$ 和 $m_i$ 互质,所以逆元一定存在)
- $x$ 的通解即为 $x = \sum_{i = 1}^n a_i t_i M_i + kM, k \in \mathbb{Z}$
扩展中国剩余定理
问题格式同上,但是没有了 $m_1, m_2, \dots, m_n$ 两两互质的条件。
引入定理:如果有特解 $x^*$,那么对于
$$ \begin{cases} x \equiv r_1 (\bmod m_1) \\ x \equiv r_2 (\bmod m_2) \end{cases} $$的通解是 $x^* + k \times \text{lcm}(m_1, m_2)$,也就是 $x \equiv x^* (\bmod \text{lcm}(m_1, m_2))$
因此,处理 exCRT 的过程就是不断从方程组内取出两个方程,尝试进行合并然后再压入方程组内,如果无解退出,否则最后方程组内剩下的唯一一个方程就是解系。
线性筛和积性函数
暂待加工。