【算法学习笔记】模运算总结

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

记号

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

[aequiv bpmod{m} ]

基本性质

模运算有一些基本性质：如果 (aequiv bpmod{m}) 且有 (cequiv dpmod{m})，那么下面的模运算律成立：

[a + cequiv b + dpmod m\ a - cequiv b - dpmod m\ a imes cequiv b imes dpmod 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(kin N)) 这些模 (5) 余 (3) 的数。 我们把满足同余关系的所有整数看作一个同余等价类。

自然地，在 (Z_n) 中的加法，减法，乘法，结果全部要在模 (n) 意义下面了，例如在 (Z_5) 中，(3 + 2 = 0,3 imes2=1)。

逆元

在实数运算下面，如果 (ab = 1)，那么可以说$ a, b$ 互为倒数，它们相乘永远得 (1)。不幸的是，(mod m) 的运算下面也有倒数的概念，而且要恐怖的多。

如果在 (Z_n) 中两元素 (a,b) 满足 (ab = 1) ，比如在 (Z_{15}) 中，(7*13 =1)，那么我们就说 (a,b) 互为模 (n) 意义下乘法的逆 ！记作 (a = b^{-1},b = a^{-1}) 。

我们知道，除以一个数等价于乘以这个数的倒数，在模运算中，除以一个数等于乘上这个数的逆（如果这个数存在乘法逆的话）！举个栗子，在 (Z_5) 中， (4÷3 = 4 imes3^{-1} = 4 imes2=3)。

看上去有点神乎其神，(4÷3) 甚至不是整数，怎么可能答案是 (3) ？？？别忘了，剩余系中每一个元素都对应一个同余等价类，所以 (4÷3=3) 的实际含义是：“假定有两个整数 (a,b) 满足 (frac ab) 是整数且(a,b) 除以 (5) 的余数分别是 (4) 和 (3) ，那么 (frac ab) 除以 (5) 的余数等于 (3) ” ，比如 (a= 9,b =3) 时就成立。

线性模方程

线性模方程是下面这玩意，其中 (x) 是未知数，我们需要做的事情是求出 (x) 的 (Z_m) 的解集。

[axequiv bpmod m ]

因为同余，所以有 (ax - b = ym) ，即 (ax - my = b) ，这个方程有解当且仅当 (gcd(a,m) | b) 。这是第一步。

假设 (a) 的逆在模 (m) 意义下存在，为 (a^{-1}) ，那么根据基本性质，两边可以同乘 (a^{-1}) ，则得到 (xequiv b imes a^{-1}pmod m) ，是不是这样，问题就轻松解决了呢？并不是，(a) 的逆极有可能在模 (m) 意义下不存在，我们试着求一下在模 (m) 意义下 (a) 的逆。即解

[axequiv 1pmod m ]

转化

[ax - 1=my ]

移项

[ax - my = 1 ]

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

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

[a'x-m'y=b'(a'=frac{a}{gcd(a,m)},m'=frac{m}{gcd(a,m)},b'=frac{b}{gcd(a,m)}) ]

于是问题回到了求解：

[a'xequiv b' (mod m') ]

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

那么这个方程的解是在 (Z_{m’}) 剩余系内的：

[xequiv(a')^{-1}b' (mod 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',...) 这些数模 mm 同余；

而 (p,p + m',p+2m',...,p+(d-1)m') 之间不可能同余，因为不满足 (i−j) 是 (d) 的倍数。所以，方程 (axequiv b pmod{m}) 要么无解，要么恰有 (gcd(a, m)) 个解。

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

中国剩余定理

更加详细的介绍：Here

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

现在有方程组 (xequiv a_i pmod {m_i})。我们令 (M = prod m_i，w_i = frac{M}{m_i})。那么解一定可以表示为$ Z_M$ 剩余系中的一个元素，即 (xequiv bpmod 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 mod m_i + 0 = 1) 即 (e_i mod m_i = 1)。

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

[x≡0+0+..+1×a_i+0+..+0pmod {m_i} ]

原因是 (e_i mod 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....x) 都是解，原方程组有无穷组实数解。

欧拉定理

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

[a^{varphi(n)} equiv 1 pmod n ]

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

[egin{aligned}a^{n - 1} equiv 1 pmod n\a^n equiv a pmod nend{aligned} ]

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

[axequiv 1pmod n ]

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

离散对数

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

[a^xequiv bpmod n ]

如果是实数范围内，答案是 (log_ab)，可惜并不是，这里采用一种精妙的解决办法。
解：根据欧拉定理有：(a^{n - 1}equiv 1pmod n)，又 (a^0equiv 1pmod n)，所以 (a^x) 在模 (n) 剩余系内的值无限循环，以 (a^0, a1,...,a{n-2}) 为循环节。
所以，只需检查 (x = 0, 1, 2,..., n - 2) 时是不是解即可。但这样复杂度是 (O(n)) 的，下面用一种构造手段将复杂度降下来：
我们先检查前 (m) 项（(m) 取值稍后说明），即 (a^0, a^1,...,a^{m - 1}) 模 (n) 的值是否为 (b)，并把 (a^imod n) 的值保存在 (e_i) 中，求出 (a^m) 逆 (a^{-m})。

下面接着考虑 (a^m, a^{m + 1},...,a^{2m - 1})，这次不需要检查，如果他们当中存在解，说明存在 (i(0le i<m)) 使得 (e_ia^mequiv bpmod n)。两边乘 (a^{-m})，得到 (e_iequiv ba^{-m}pmod n)，也就是说我们只需要检查有没有一个 (i)，使得 (e_iequiv ba^{-m}pmod n)，这相当于依次检查了 (a^m, a^{m + 1},...,a^{2m - 1})。

如果仍然没有检查到解，这回考虑 (a^{2m}, a^{2m + 1},...,a^{3m - 1})，同样的，我们只需要检查有没有一个 (i)，使得 (e_iequiv b(a{-m})2pmod n)，这相当于依次检查了 (a^{2m}, a^{2m + 1},...,a^{3m - 1})。

显然使用 STL 中的 MAP 可以帮我们快速完成检测操作。预处理出 (e_i) 的复杂度是 (O(mlog m))，求出 (a^{-m}) 的复杂度是 (log n)，一共有 (n/m) 轮检测，每轮复杂度 (log m)。总复杂度 (O((m + frac{n}{m})log m)) ，当 (m = sqrt n) 时，复杂度最低为：(O(sqrt nlog n))

指数循环节

[a^{x} equiv b pmod n ]

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

[a^{x} equiv a^{x mod varphi(n)} pmod n ]

如果 (gcd(a,n) ot =1) ，似乎不好做了，不过也有公式！

[a^xequiv a^{x mod varphi(n) + varphi(n)} pmod n (xge varphi(n)) ]

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

关于 (gcd(a,n) ot =1) 的公式参考：Here