Sengxian's Blog

模运算是一个高深的地方，初来乍到，还是写一下为敬QAQ。。。

记号

我们把 $a$ 除以 $m$ 所得的余数记作 $a \bmod m$。
如果 $a \bmod m = b \bmod m$，即 $a$, $b$ 除以 $m$ 所得的余数相等，那么我们记作：

基本性质

模运算有一些基本性质：如果 $a\equiv b\pmod{m}$ 且有 $c\equiv d\pmod{m}$，那么下面的模运算律成立：

这就是我们平常经常利用的性质，如果答案对一个数取模，那么模了再加，乘，减都是不影响答案的。特别注意除法是没有这个性质的！

剩余系

如果一个剩余系中包含了这个正整数 $n$ 所有可能的余数（一般地，对于任意正整数 $n$，有 $n$ 个余数：$0,1,2,...,n-1$），那么就被称为是模 $n$ 的一个完全剩余系，记作 $Z_n$；而简化剩余系就是完全剩余系中与 $n$ 互素的数的那些元素，记作 $Z_n^*$。
$Z_n$ 里面的每一个元素代表所有模 $n$ 意义下与它同余的整数。例如 $n = 5$ 时，$Z_5$ 的元素 $3$ 实际上代表了 $3, 8, 13, 18,....,5k + 3(k\in N)$ 这些模 $5$ 余 $3$ 的数。 我们把满足同余关系的所有整数看作一个同余等价类。
自然地，在 $Z_n$ 中的加法，减法，乘法，结果全部要在模 $n$ 意义下面了，例如在 $Z_5$ 中，$3 + 2 = 0, 3 \times 2 = 1$。

逆元

在实数运算下面，如果 $ab = 1$，那么可以说 $a, b$ 互为倒数，它们相乘永远得 $1$。不幸的是，$\bmod m$ 的运算下面也有倒数的概念，而且要恐怖的多。
如果在 $Z_n$ 中的两元素 $a$, $b$ 满足 $ab = 1$，比如在 $Z_{15}$ 中，$7*13 = 1$，那么我们就说 $a,b$ 互为模 $n$ 意义下乘法的逆！记作 $a = b^{-1}, b = a^{-1}$。
我们知道，除以一个数的等于乘这个数的倒数，在模运算中，除以一个数等于乘上这个数的逆（如果这个数存在乘法逆的话）！举例说明，在 $Z_5$ 中，$4 \div 3 = 4 \times 3^{-1} = 4 \times 2 = 3$。
看上有点神乎其神，$4 \div 3$ 甚至不是整数，怎么可能答案是 $3$？？？别忘了，剩余系中的每一个元素都对应一个同余等价类，所以 $4 \div 3 = 3$ 的实际含义是：“假定有两个整数 $a, b$, 满足 $\frac{a}{b}$ 是整数，且 $a, b$ 除以 $5$ 的余数分别是 $4$ 和 $3$，那么 $\frac{a}{b}$ 除以 $5$ 的余数等于 $3$”，比如 $a = 9, b = 3$ 时就成立。

线性模方程

线性模方程是下面这个玩意，其中 $x$ 是未知数，我们要干的事情就是求出 $x$ 在 $Z_m$ 中的解集。

因为同余，所以有 $ax - b = ym$，即 $ax - my = b$，这个方程有解当且仅当 $\gcd(a, m) \mid b$。这是第一步。
假设 $a$ 的逆在模 $m$ 意义下存在，为 $a^{-1}$，那么根据基本性质，两边可以同乘 $a^{-1}$，则得到 $x\equiv b\times a^{-1} \pmod{m}$，是不是这样，问题就轻松解决了呢？并不是，$a$ 的逆极有可能在模 $m$ 意义下不存在，我们试着求一下在模 $m$ 意义下 $a$ 的逆。即解

转化：

移项：

根据扩展欧几里得算法，当且仅当 $\gcd(a, m) = 1$，模 $m$ 意义下 $a$ 的逆存在。所以，我们要解 $ax\equiv b \pmod{m}$，必须将其转化，使得 $a$ 的乘法逆存在。

将 $ax - my = b$ 两边同时除以 $\gcd(a, m)$，得到：

于是问题回到了求解：

这一回，我们能保证 $\gcd(a', m') = 1$，所以 $a$ 在这里一定有乘法逆！

那么这个方程的解是在 $Z_{m'}$ 剩余系内的：

但是我们需要求解的是 $Z_{m}$ 剩余系内的元素，怎么转换过去呢？设 $p = (a')^{-1}b'$，那么我们有无穷多个实数解：$x = p, p + m', p + 2m', p + 3m'...$。我们想要知道，这无穷多个实数解，在模 $m$ 意义下究竟有多少个等价类（即模 $n$ 会有多少个不同的余数）？大家可能已经发现了，正好 $d = \gcd(a, m)$ 个，分别为 $p, p + m', p + 2m',...,p + (d - 1)m'$。
为什么呢？假设 $p + im'$ 与 $p + jm'$ 模 $m$ 同余，那么 $(p + im') - (p + jm') = (i - j)m'$，必定是 $m$ 的倍数，也就是 $i - j$ 是 $d$ 的倍数。所以是 $d$ 个一轮回的！
$p, p + dm', p + 2dm',...$ 这些数模 $m$ 同余；
$p + m', p + (d + 1)m', p + (2d + 1)m',...$ 这些数模 $m$ 同余；
...
$p + (d - 1)m', p + (d + d - 1)m', p + (2d + d - 1)m',...$ 这些数模 $m$ 同余；
而 之间不可能同余，因为不满足 $i - j$ 是 $d$ 的倍数。所以，方程 $ax\equiv b \pmod{m}$ 要么无解，要么恰有 $\gcd(a, m)$ 个解。

总结起来，解线性同余方程只需要求 $a$ 的乘法逆，但分析过程还是有些恼人的。

中国剩余定理

现在如果有多个同余方程，即同余方程组，变量只有一个，且 $x$ 前面系数为 $1$， 任意 $m_i$ 之间互素，该怎么做呢？
中国剩余定理在这里派上用场了，它并不是一种算法，而是一种思考、构造的方法。

现在有方程组 $x\equiv a_i \pmod {m_i}$。我们令 $M = \prod m_i$，$w_i = \frac{M}{m_i}$。那么解一定可以表示为 $Z_M$ 剩余系中的一个元素，即 $x\equiv b\pmod M$。我们来构造这个解。

由于 $m_i$ 之间互素，可以得到 $\gcd(m_i, w_i) = 1$，构造出这样一个方程 $w_ip_i + m_iq_i = 1$，由于 $\gcd(m_i, w_i) = 1$，此方程一定有解。用扩展欧几里得算法解出 $p_i, q_i$，令 $e_i = w_ip_i$，现在有一些有趣的性质，方程两边都模 $m_i$，得到 $e_i \bmod m_i + 0 = 1$ 即 $e_i \bmod m_i = 1$。

依据这一性质，我们构造得到方程在 $Z_M$ 剩余系中的唯一解 $x \equiv e_1a_1 +e_2a_2 +...+e_na_n\pmod M$。验证一下，只需把每个方程带进去，看是否都成立即可。对于 $x\equiv a_i \pmod {m_i}$，将得到的解右边模 $m_i$，惊奇的发现，除了 $e_ia_i$ 这一项的结果为 $a_i$ 之外，其余项的结果都是 $0$。

原因是 $e_i \bmod m_i = 1$ 一模变成 $1$，还有 中 $w_j$ 必定含有因子 $m_i$，所以一模就成 $0$ 了。

则对于每一个 $m_i$，我们都能得到一个与原方程组一模一样的同余等式，所以这个解是正确的。

所以 $x_0 = e_1a_1 +e_2a_2 +...+e_na_n$ 显然是一个实数解，$x_0 + M, x_0 +2M, x_0 + 3M....$ 都是解，原方程组有无穷组实数解。

欧拉定理

在数论中，欧拉定理是一个关于同余的性质。欧拉定理表明，若 $n, a$ 为正整数，且 $n,a$ 互素，则：

特别的，当 $n$ 为素数的时候，$a$ 可取任意 $Z_n$ 内元素。由于 $\varphi(n) = n - 1$，故有：

这就是费马小定理。观察到右边 $1$ 的存在，发现与之前所说的逆元有一点相似：

$x$ 是逆元，根据费马小定理，有 $x \equiv a^{n-2} \pmod n$，故可以快速幂在 $O(\log n)$ 的时间内快速求出任意 $Z_n$ 内元素的逆元，但只有在 $n$ 是素数的时候才起作用。

离散对数

当 $n$ 为素数的时候，解模方程：

如果是实数范围内，答案是 $\log_ab$，可惜并不是，这里采用一种精妙的解决办法。
解：根据欧拉定理有：$a^{n - 1}\equiv 1\pmod n$，又 $a^0\equiv 1\pmod n$，所以 $a^x$ 在模 $n$ 剩余系内的值无限循环，以 $a^0, a^1,...,a^{n-2}$ 为循环节。
所以，只需检查 $x = 0, 1, 2,..., n - 2$ 时是不是解即可。但这样复杂度是 $O(n)$ 的，下面用一种构造手段将复杂度降下来：
我们先检查前 $m$ 项（$m$ 取值稍后说明），即 $a^0, a^1,...,a^{m - 1}$ 模 $n$ 的值是否为 $b$，并把 $a^i\bmod n$ 的值保存在 $e_i$ 中，求出 $a^m$ 逆 $a^{-m}$。
下面接着考虑 $a^m, a^{m + 1},...,a^{2m - 1}$，这次不需要检查，如果他们当中存在解，说明存在 $i(0\le i<m)$ 使得 $e_ia^m\equiv b\pmod n$。两边乘 $a^{-m}$，得到 $e_i\equiv ba^{-m}\pmod n$，也就是说我们只需要检查有没有一个 $i$，使得 $e_i\equiv ba^{-m}\pmod n$，这相当于依次检查了 $a^m, a^{m + 1},...,a^{2m - 1}$。
如果仍然没有检查到解，这回考虑 $a^{2m}, a^{2m + 1},...,a^{3m - 1}$，同样的，我们只需要检查有没有一个 $i$，使得 $e_i\equiv b(a^{-m})^2\pmod n$，这相当于依次检查了 $a^{2m}, a^{2m + 1},...,a^{3m - 1}$。
显然使用 STL 中的 MAP 可以帮我们快速完成检测操作。预处理出 $e_i$ 的复杂度是 $O(m\log m)$，求出 $a^{-m}$ 的复杂度是 $\log n$，一共有 $n/m$ 轮检测，每轮复杂度 $\log m$。总复杂度 $O((m + \frac{n}{m})\log m)$，当 $m = \sqrt n$ 时，复杂度最低为：$O(\sqrt n\log n)$

指数循环节

当 $x$ 大到一定程度的时候，我们没有办法算 $b$ 了，这时需要用到指数循环节。
如果 $\gcd(a, n) = 1$，由欧拉定理 $a^{\varphi(n)} \equiv 1 \pmod n$ 可知指数以 $[0, \varphi(n) - 1]$ 为循环节不断循环，故有

如果 ，似乎不好做了，不过也有公式！

需要声明一下，只有 $x\ge \varphi(n)$ 时此公式成立，所以千万不要盲目的取余了再加！