【算法學習筆記】模運算總結

模運算是一個高深的地方，初來乍到，還是寫一下為敬QAQ。。。

記号

我們把 \(a\) 除以 \(m\) 所得的餘數記作 \(a \bmod m\)。

如果 \(a \bmod m = b \bmod m\)，即 \(a\), \(b\) 除以 \(m\) 所得的餘數相等，那麼我們記作：

\[a\equiv b\pmod{m}

\]

基本性質

模運算有一些基本性質：如果 \(a\equiv b\pmod{m}\) 且有 \(c\equiv d\pmod{m}\)，那麼下面的模運算律成立：

\[a + c\equiv b + d\pmod m\\

a - c\equiv b - d\pmod m\\

a \times c\equiv b \times 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\times2=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÷3 = 4\times3^{-1} = 4 \times2=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\) 的解集。

\[ax\equiv b\pmod m

因為同餘，是以有 \(ax - b = ym\) ，即 \(ax - my = b\) ，這個方程有解當且僅當 \(gcd(a,m) | b\) 。這是第一步。

假設 \(a\) 的逆在模 \(m\) 意義下存在，為 \(a^{-1}\) ，那麼根據基本性質，兩邊可以同乘 \(a^{-1}\) ，則得到 \(x\equiv b\times a^{-1}\pmod m\) ，是不是這樣，問題就輕松解決了呢？并不是，\(a\) 的逆極有可能在模 \(m\) 意義下不存在，我們試着求一下在模 \(m\) 意義下 \(a\) 的逆。即解

\[ax\equiv 1\pmod m

轉化

\[ax - 1=my

移項

\[ax - my = 1

根據擴充歐幾裡得算法，當且僅當 \(gcd(a,m) = 1\) ，模 \(m\) 意義下 \(a\) 的逆存在。是以，我們要解 \(ax\equiv 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'x\equiv b'\ (mod\ m')

這一回，我們能保證 \(gcd(a’,m’) = 1\) ，是以 \(a\) 在這裡一定有乘法逆！

那麼這個方程的解是在 \(Z_{m’}\) 剩餘系内的：

\[x\equiv(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\) 的倍數。是以，方程 \(ax\equiv b \pmod{m}\) 要麼無解，要麼恰有 \(\gcd(a, m)\) 個解。

總結起來，解線性同餘方程隻需要求 \(a\) 的乘法逆，但分析過程還是有些惱人的。

中國剩餘定理

更加詳細的介紹：Here

現在如果有多個同餘方程，即同餘方程組，變量隻有一個，且 \(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\)。

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

原因是 \(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....x\) 都是解，原方程組有無窮組實數解。

歐拉定理

在數論中，歐拉定理是一個關于同餘的性質。歐拉定理表明，若 \(n,a\) 為正整數，且 \(n,a\) 互素，則：

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

特别的，當 \(n\) 為素數的時候，aa 可取任意 \(Z_n\) 内元素。由于 \(\varphi(n) = n - 1\)，故有：

\[\begin{aligned}a^{n - 1} \equiv 1 \pmod n\\a^n \equiv a \pmod n\end{aligned}

這就是費馬小定理。觀察到右邊 \(1\) 的存在，發現與之前所說的逆元有一點相似：

\[ax\equiv 1\pmod n

\(x\) 是逆元，根據費馬小定理，有 \(x \equiv a^{n-2} \pmod n\)，故可以快速幂在 \(O(\log n)\) 的時間内快速求出任意 \(Z_n\) 内元素的逆元，但隻有在 \(n\) 是素數的時候才起作用。

離散對數

當 \(n\) 為素數的時候，解模方程：

\[a^x\equiv b\pmod n

如果是實數範圍内，答案是 \(\log_ab\)，可惜并不是，這裡采用一種精妙的解決辦法。

解：根據歐拉定理有：\(a^{n - 1}\equiv 1\pmod n\)，又 \(a^0\equiv 1\pmod 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^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)\)

指數循環節

\[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 \bmod \varphi(n)} \pmod n

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

\[a^x\equiv a^{x \bmod \varphi(n) + \varphi(n)} \pmod n (x\ge \varphi(n))