基礎數論 - HackMD

--- title: 基礎數論 --- # 基礎數論 --- ### Tips 二進位的處理，使用**位元運算** ```a >> 1``` 代表將其二進位右移一位 等價於 ```a / 2``` ```a & 1``` 代表將其二進位最低位取出 等價於 ```a % 2``` ---- ### ```a & 1``` | | | | | --- | --- | ---- | | | 12 | 1100 | | & | 1 | 0001 | | | 0 | 0000 | ---- ### ```a & 1``` | | | | | --- | --- | ---- | | | 13 | 1101 | | & | 1 | 0001 | | | 1 | 0001 | --- ## Basics ---- ### 除法演算法 $m = nq + r$，其中 $0 \leq r < n$ 記作 $r = m \bmod n$ ```m % n``` ---- ### 因數 $r$ 同時為 $n$ 和 $m$ 的因數 則稱 $r$ 為 $n$ 和 $m$ 的 **公因數** 最大的 $r$ 又稱為 **最大公因數** ---- ### 倍數 $r$ 同時為 $n$ 和 $m$ 的倍數 則稱為 **公倍數** 最小的 $r$ 稱為 **最小公倍數** ---- ### 互質 $\gcd(a, b) = 1$，稱 $a, b$ **互質** --- ## 最大公因數 ---- ### $\gcd$ & $\text{lcm}$ - $\gcd$ = **G**reatest **C**ommon **D**ivisor - $\text{lcm}$ = **L**east **C**ommon **M**ultiple ---- ### 輾轉相除法 $m = nq + r$ $\gcd(m, n) = \gcd(n, r)$ 不斷地利用除法演算法 便能將求最大公因數之問題規模縮小 此算法稱為歐幾里得算法 為求方便定義 $\gcd(n, 0) = n$ Note: 講義有證明 ---- ### 輾轉相除法 ```cpp= def gcd(a, b): if b == 0: return a return gcd(b, a % b) ``` ---- ### 複雜度不斷折半 $\text{O}(\log(\max(a,\ b)))$ ---- ### 最小公倍數求法 $\ \gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b$ --- ## 質數 ---- ### 定義當 $m$ 只有二個因數我們稱 $m$ 為**質數** 不是質數的數則被稱為**合數** ---- ### Why we need primes? 質數在乘法中是不可被拆解的單位其也在數論中扮演重要的角色 ---- ### 篩法一個合數必定是某個質數的倍數把不可能成為質數的合數**篩**掉留下的數字就會是質數 ---- ### Sieve of Eratosthenes 埃氏篩法 - 從 $2$ 開始往上 - 遇到質數就把它的倍數標記為合數 - 遇到合數跳過即可 ---- ### Example | | | | | | | | | | | | ----------------------------------------------------------------------------- | --------------------------------------------------------------------------- | ----------------------------------------------------------------------------- | ---------------------------------------------------------------------- | --------------------------------------------------------------------------- | ---------------------------------------------------------------------- | ----------------------------------------------------------------------------- | ---------------------------------------------------------------------- | ----------------------------------------------------------------------------- | ----------------------------------------------------------------------- | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | ---- ### 時間複雜度 $\text{O}(n\cdot \log(\log n))$ $n + \frac n2 + \frac n3 + \cdots + \frac nn \approx n\log n$ $\frac n2 + \frac n3 + \frac n5 + \cdots + \frac np \approx n\log (\log n)$ ---- ### 實作 1. 使用迴圈從小到大列舉數字 2. 配合陣列去紀錄每個數是不是一個質數 Note: 給個 3min 劇透限制 ---- ### 實作 ```cpp= [|1|2|4|5-8|5|6|7|8] const int N = 20000000; bool notprime[N+5]; void eratosthenes_sieve() { notprime[0] = notprime[1] = true; for (int i = 2; i * i <= N; ++i) if (!notprime[i]) for (int j = i * 2; j <= N; j += i) notprime[j] = 1; } ``` Note: | Line | 說明 | | ---- | ----------------------------------------------------------------------------------------------------- | | 10 | 由於一開始會先假設所有數為質數後再一一標記為合數 所以通常會先將質數指定為 false 而省去初始化的時間 | | 14 | // sqrt(N) 以上的數字不會篩掉任何數字了 | ---- ### Tips 如果你不喜歡 ```i * i <= N``` 也可以寫成 ```i <= sqrt(N)``` ---- ### 優化 - $2$ 獨立處理，列舉質數的迴圈只跑奇數 - 多一個 $\text{if}$ 判斷是否為合數倍 - 欲刪掉質數 $i$ 的倍數時 $2 \sim (i-1)$ 倍一定被篩過了 只需要篩 $i$ 倍以上的數 Note: 合數倍已被篩過 ---- ### Linear Sieve 線性篩法埃氏篩法把++質數的倍數++篩掉線性篩法把++每個數的質數倍++篩掉 ---- ### 想法目標是讓每個合數都只被篩到 $1$ 次我們把任一個合數寫成質數相乘的形式 $\qquad C = p_1p_2\dots p_n$ 想辦法讓 $C$ 只被 $p_2\dots p_n$ 篩到 ---- ### 實作 ```cpp= [|1|2|3|7-17|7|8-9|10|11-12|13|14-15] const int N = 20000000; bool notprime[N+5]; vector<int> prime; void linear_sieve() { for (int i = 2; i <= N; ++i) { if (!notprime[i]) prime.push_back(i); for (auto p1 : prime) { if (p1 * i > N) break; notprime[p1 * i] = true; if (i % p1 == 0) break; } } } ``` Note: | Line | 說明 | | 7 | 列舉 p2 * ... * pn | | 8-9 | 順便找質數 | | 10 | 列舉當前找到的質數 | | 11-12 | 後面列舉的質數仍會超過範圍，skip | | 13 | 標記合數 | | 14-15 | 從小到大地去列舉質數 $p_1$ 若 $i = p_2\dots p_n$ 被 $p_1$ 整除 則 $p_1 = p_2$ 根據需求，不需要再去列舉更大的 $p_1$ 了 所以此時就可以 `break` 了 | ---- ### 分析比較 * **不用把篩出的質數儲存** 在 $2\times 10^8$ 範圍優化過的 ++埃氏篩法++ 較快 * **須把篩出的質數儲存** ++線性篩法++ 稍微快一點 (大概不到 10%) 因為不用額外優化 code 短一些 ---- ### 篩法 DP 在篩法過程中，把篩法表型別由 bool 改成 int **存當前數字被哪個質數篩掉。** 將原為 bool 陣列的 ```notprime``` 改為 int 陣列的 ```sieve``` ---- ### 子問題篩法結束後，對於任意數字 $i$ 其 $\text{sieve}[i]$ 為 $i$ 的任一質因數由於 $\text{sieve}[i]$ 必定**整除** $i$ **$dp_{i / \text{sieve}[i]}$** 會變成 $dp_i$ 的**同性質子問題**。 ---- ### Hints 我們讓質數 $p$ 的 $\text{sieve}[p] = p$ 而不是 $0$ 可以方便 DP 處理 ---- ### Example **拿來求質因數個數(重複)** ```cpp= [|1|2] dp[1] = 0; dp[i] = dp[i / sieve[i]] + 1; ``` Note: 線性複雜度獲得所有數的質因數個數 ---- ### Example **拿來求質因數個數（重覆不算）** ```cpp= [|1|2-4|3|4|5] dp[1] = 0; int t = i; while (t % sieve[i] == 0) t /= sieve[i]; dp[i] = dp[t] + 1; ``` Note: 多了個超小的 $\log$ 讓 $i$ 把質因數 $\text{sieve}[i]$ 除乾淨此時 $t$ 滿足 ```t % sieve[i] != 0``` ```dp[t]``` 是同性質小問題 而 $i$ 一定比 $t$ 多一個不重覆的質因數 $\text{sieve}[i]$ ---- ### Example **拿來求各質因數次數** ```cpp= [|1|2-3|2|3] memset(dp[1], 0, sizeof(dp[1])) memcpy(dp[i], dp[i / sieve[i]], sizeof(dp[0])); ++dp[i][idx[sieve[i]]]; ``` Note: ```dp[i][j] = k``` 記錄整數 $i$ 擁有第 $j$ 小的質數 $k$ 次方則整數 $i$ 一定剛好比整數 $i / \text{sieve}[i]$ 多擁有 $1$ 次方的 $\text{sieve}[i]$ 其它一樣 ---- ### Example **也可以不 DP 直接求** 比如說質因數個數（重覆也算） ```cpp= int ans = 0; while (n > 1) ans++, n /= sieve[n]; ``` 不需要把每個數的個數算出來 ---- ### 練習題 - [Zerojudge a007 判斷質數](https://zerojudge.tw/ShowProblem?problemid=a007) - [Zerojudge f803 質數篩法練習](https://zerojudge.tw/ShowProblem?problemid=f803) - [Luogu P1865 A % B Problem](https://www.luogu.com.cn/problem/P1865) - [toj 183 哭力怕運算](https://toj.tfcis.org/oj/pro/183/) - [toj 442 簡單數學](https://toj.tfcis.org/oj/pro/442/) --- ## 同餘 ---- ### 定義二個數 $a,\,b$ 滿足 $m\ |\ a − b$ 那我們說這兩個數模 $m$ 同餘 記為 $a \equiv b \pmod m$ ---- ### 優點整數的剩餘系具有許多優點 1. 它具有良好的代數性質 2. 在程式計算中 它將會是一個避免整數 $\text{overflow}$ 的工具 ---- ### Properties * 同加 $\begin{align*} &A\ \equiv\ B\\ \Rightarrow\ &A+C\ \equiv\ B+C\\ \end{align*}$ * 同減 $\begin{align*} &A\ \equiv\ B\\ \Rightarrow\ &A-C\ \equiv\ B-C\\ \end{align*}$ * 同乘 $\begin{align*} &A\ \equiv\ B\\ \Rightarrow\ &A×C\ \equiv\ B×C\\ \end{align*}$ ---- ### Warning 沒有除法 ---- ### 小結以上的性質可以得到一個結論在大部分的運算中 **計算完再取模**跟**先取模再計算** 得出來的答案是相同的！ --- ## 歐拉函數 ---- ### Why we need this? 歐拉函數 Euler's Totient Function 數論中的重要函數 $\phi(n)$ 為 $0 \sim (n - 1)$ 中與 $n$ 互質的數 e.g. $\phi(2) = 1,\, \phi(6) = 2,\, \phi(7) = 6$ ---- ### 定義 **完全剩餘系**定義為一大小為 $n$ 的集合 其每個元素$\bmod n$ 後會有相異 $n$ 個元素 $0,1,\dots,n-1$ 為$\bmod n$ 的**非負最小完全剩餘系** ---- ### 定義 **簡化剩餘系** 則是將完全剩餘系中與 $n$ 互質的數留下 **非負最小簡化剩餘系** 即由 $0 \sim (n - 1)$中與 $n$ 互質的數組成 定義歐拉函數 $\phi(n)$ 為簡化剩餘系的元素數量 ---- ### Example 考慮$\bmod 6$ 的情況 **完全剩餘系** $\{1,2,3,4,5,6\} \text{ or } \{0,7,-4,3,40,-25 \}$ **非負最小完全剩餘系**唯一為 $\{0,1,2,3,4,5\}$ **非負最小簡化剩餘系**唯一為 $\{1,5\}$ $\phi(6) = 2$ ---- ### 定理 $N = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$ 其中 $p_i$ 為 $N$ 的質因數 \begin{equation} \phi(N) = N \displaystyle\prod_{i}(1 - \frac{1}{p_i}) \end{equation} 證明略 Note: 與哪些質數有關，與冪次無關 ---- ### Example $6 = 2 \times 3$ \begin{align} \phi(6) &= 6 \cdot (1 - \frac12)(1 - \frac13)\\ &= 6 \cdot \frac12 \cdot \frac23 \\ &= 2 \end{align} e.g. $1,\,5$ ---- ### Example $18 = 2 \cdot 3^2$ \begin{align} \phi(18) &= 18 \cdot (1 - \frac12)(1 - \frac13)\\ &= 18 \cdot \frac12 \cdot \frac23 \\ &= 6 \end{align} e.g. $1, 5, 7, 11, 13, 17$ ---- ### 求法歐拉函數具有以下性質 \begin{equation} n = \sum_{d | n} \phi(d) \end{equation} $\phi(n) = n - \sum_{d | n,\ d \lt n} \phi(d)$ Note: $\gcd(k, n) = d \Rightarrow \gcd(\frac kd, \frac nd) = 1$ 令 $f(x)$ 為 $\gcd(k, n) = x$ 的個數 ---- ### 求法比起列舉因數 (每個 $\sqrt{k}$) 不如直接列舉倍數 (共 $n \log n$) ---- ### 實作 ```cpp= [|2-3|4-6|4-5|6] void sieve(int N) { for (int i = 1; i <= N; ++i) phi[i] = i; // 一開始讓 phi_i = i for (int i = 1; i <= N; ++i) for (int j = 2 * i; j <= N; j += i) phi[j] -= phi[i]; } ``` ---- ### 篩法求法 - 埃式篩法 + 篩法 DP 利用 $\text{Formula }1$ 配合篩法 DP 枚舉出所有質因數直接進行質因數分解 - 線性篩法在每個數被篩到時 順便根據公式去計算它的歐拉函數 Note: 不細講 ---- ### 單個求法 - 單個數的 $\sqrt N$ 求法沒有需要求出大範圍的歐拉函數的話 可以一個一個求直接利用 $\text{Formula 1}$ + $\sqrt N$ 列舉質因數 可得一 $\text{O}(\sqrt N)$ 的作法。 Note: 質因數分解 ---- ### 練習題 - [toj 427 誘惑之森](https://toj.tfcis.org/oj/pro/427/) --- ## 歐拉定理 ---- ### 定理內容 $m^{\phi(n)} \equiv 1 \pmod n$ $\text{ when } \gcd(m, n) = 1$ ---- ### 引理 $am \equiv bm \Leftrightarrow a\equiv b \pmod n \text{ when }\gcd(m, n) = 1$ \begin{align} & am \equiv bm \pmod n \\ \Rightarrow\, & n\, |\, (a-b)m \\ \Rightarrow\, & n\, |\, (a-b) \\ \Rightarrow\, & a\equiv b\pmod n \end{align} ---- #### 費馬小定理 $a^{p-1} \equiv 1 \pmod p$ Note: $\phi(p) = p-1$ ---- ### 廣義歐拉定理 \begin{equation} a^b \equiv \begin{cases} a^{b \bmod \phi(m)} & \gcd(a, m) = 1\\ a^b & \gcd(a, m) \neq 1,\ b \lt \phi(m)\\ a^{b \bmod \phi(m) + \phi(m)} & \gcd(a, m) \neq 1,\ b \ge \phi(m) \end{cases} \quad \pmod m \end{equation} ---- ### Example $4^k \pmod {18}$ $1,\,4,\,16,\,10,\,4,\,16,\,10,\,4,\,16,\,10,\,4,\,16,\,\dots$ Note: $\phi(18) = 6$ ---- ### 小結透過計算歐拉函數配過廣義歐拉定理來**降冪** 求解 $a^b \bmod m$ 時可以減少需要計算的次方 ---- ### 練習題 - [TIOJ 1324 指數之謎](https://tioj.ck.tp.edu.tw/problems/1324) --- ## 擴展歐幾里得算法 ---- ### Why we need it? **擴展歐幾里得算法** ($\text{Extended Euclid's Algorithm}$) 用於求出形式如$\text{ ax + by = c }$的整數解 Note: 但在使用它之前，需要一些定理來輔助證明此算法的正確性 ---- ### 定理１假設 $m, n \in \mathbb Z,\ g = \gcd(m, n)$, 則 $\{ms + nt\, |\, s, t \in \mathbb Z\} = \{gx\ |\ x \in \mathbb Z\}$ Note: :::spoiler 證明當 $m = n = 0$ 時，顯然成立因此我們可以假設 $m \neq 0$ 或 $n \neq 0$ 假設 $I = \{ms + nt\ |\ s, t \in \mathbb Z\}$，$k$ 為 $I$ 中的最小正整數欲證 $I = \{kx\ |\ x \in \mathbb Z\} \enspace \forall c \in I, c \neq 0$ 根據除法演算法，存在 $q, r \in \mathbb Z$ 使得 $c = qk + r, 0 \leq r \lt k \Rightarrow r = c - qk$ 因為 $c \in I$ 且 $k \in I$，所以 $r \in I$ 因為 $k$ 為 $I$ 中最小正整數且 $r \lt k$，所以 $r = 0$ $\Rightarrow c = kq \in \{kx | x \in \mathbb Z\}$，因此 $I = \{kx | x \in \mathbb Z\}$ 接著證明 $k = g$ 因為 $m, n \in I = \{kx | x \in \mathbb Z\}$，所以 $m, n$ 皆為 $k$ 的倍數，因此 $k$ 為 $m, n$ 的公因數因為 $k \in I$，所以 $\exists s, t \in Z$ 使得 $k = ms + nt$ 因此，若 $d$ 為 $m, n$ 的公因數，則 $d$ 為 $k$ 因數 $\Rightarrow |d| \leq k$，所以 $k$ 為 $m, n$ 的最大公因數，即 $k = g$ ::: ---- ### 定理２ (貝祖定理) 假設 $a, b, c \in \mathbb Z^+$，則 $\text{Diophantine}$ 方程式 $ax + by = c$ 有整數解 $x = x_0$，$y = y_0$ 若且唯若 $\text{gcd}(a, b)\,|\,c$ Note: :::spoiler 證明 $(\Rightarrow):$ 因為 $ax + by = c$ 有整數解 $x = x_0$，$y = y_0$，所以 $ax_0 + by_0 = c$ 因為 $\gcd(a, b)|a$ 且 $\gcd(a, b)|b$，所以 $\gcd(a, b)|c$ $(\Leftarrow):$ 因為 $\gcd(a, b)|c$，所以 $c = \gcd(a, b)d, \text{ for some } d \in \mathbb Z$ 因為 $\exists s, t \in \mathbb Z$ 使得 $\gcd(a, b) = as + bt$ 所以 $a(sd) + b(sd) = \gcd(a, b)d = c$ $\Rightarrow ax + by$ 有整數解 $x_0 = sd$，$y_0 = td$ ::: ---- ### 解法 $ax + by = \gcd(a,b)$ $bx' + (a \bmod b)y' = \gcd(b, a \bmod b)$ $bx' + (a \bmod b)y' = \gcd(a, b)$ ---- ### 解法 $bx' + (a \bmod b)y' = \gcd(a, b)$ $bx' + (a - b\left\lfloor\frac{a}{b}\right\rfloor)y' = \gcd(a, b)$ $ay' + b(x' - \left\lfloor\frac{a}{b}\right\rfloor y') = \gcd(a, b)$ ---- ### 解法 $ay' + b(x' - \left\lfloor\frac{a}{b}\right\rfloor y') = \gcd(a, b)$ \begin{cases} x = y' \\ y = x' - \lfloor \frac a b \rfloor y' \end{cases} Note: 因此只要算出 $(b,\ a \bmod b)$ 的解即可回推出 $(a,\ b)$ 的解欲算出 $(b,\ a \bmod b) \triangleq (a',\ b')$ 的解又可以先求出 $(b',\ a' \bmod b')$ 的解 ---- ### 最小子問題假設二數的最大公因數是 $g$ 則最小的子問題跟歐幾里得算法一樣是 $(g, 0)$ $gx + 0y = g$ $(x,\ y) = (1,\ 0)$ ----  ### Example \begin{align} &16x + 10y = 2 &\quad &16 = 10 \times 1 + 6 \\ &10x + 6y = 2 &\quad &10 = 6 \times 1 + 4 \\ &6x + 4y = 2 &\quad &6 = 4 \times 1 + 2 \\ &4x + 2y = 2 &\quad &4 = 2 \times 2 + 0 \\ &2x + 0y = 2 &\quad &(x, y) = (1, 0) \\ \end{align} ----  ### Example \begin{align} &16x + 10y = 2 &\quad &16 = 10 \times 1 + 6 \\ &10x + 6y = 2 &\quad &10 = 6 \times 1 + 4 \\ &6x + 4y = 2 &\quad &6 = 4 \times 1 + 2 \\ &4x + 2y = 2 &\quad &(x, y) = (0, 1) \\ &2x + 0y = 2 &\quad &(x, y) = (1, 0) \\ \end{align} ----  ### Example \begin{align} &16x + 10y = 2 &\quad &16 = 10 \times 1 + 6 \\ &10x + 6y = 2 &\quad &10 = 6 \times 1 + 4 \\ &6x + 4y = 2 &\quad &(x, y) = (1, -1) \\ &4x + 2y = 2 &\quad &(x, y) = (0, 1) \\ &2x + 0y = 2 &\quad &(x, y) = (1, 0) \\ \end{align} ----  ### Example \begin{align} &16x + 10y = 2 &\quad &16 = 10 \times 1 + 6 \\ &10x + 6y = 2 &\quad &(x, y) = (-1, 2) \\ &6x + 4y = 2 &\quad &(x, y) = (1, -1) \\ &4x + 2y = 2 &\quad &(x, y) = (0, 1) \\ &2x + 0y = 2 &\quad &(x, y) = (1, 0) \\ \end{align} ----  ### Example \begin{align} &16x + 10y = 2 &\quad &(x, y) = (2, -3) \\ &10x + 6y = 2 &\quad &(x, y) = (-1, 2) \\ &6x + 4y = 2 &\quad &(x, y) = (1, -1) \\ &4x + 2y = 2 &\quad &(x, y) = (0, 1) \\ &2x + 0y = 2 &\quad &(x, y) = (1, 0) \\ \end{align} ---- ### 實作方式 ```cpp= int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } ``` Note: 預留 3min 劇透線 ---- ### 實作方式 ```cpp= [|1|2-6|7-13|8-9|10-11|12|3-4|5] int extgcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } else { int x_, y_; int g = extgcd(b, a % b, x_, y_); x = y_; y = x_ - (a / b) * y_; return g; } } ``` Note: 計算子問題的解最小子問題解 ---- ### 精簡實作版 ```cpp= [|3] void extgcd(int a, int b, int& x, int& y) { if (b) { extgcd(b, a%b, y, x); y -= (a / b) * x; } else x = 1, y = 0; } ``` ---- ### 複雜度以歐幾里得算法 $(\gcd)$ 實作 $\text{O}(\log(\max(a,\ b)))$ ---- ### 解的情況欲解 $ax+by=c$, 只需先求出 $ax+by=\gcd(a, b)$ 的解 再把解乘上 $\frac c{\gcd(a, b)}$ 即可 $\gcd(a, b) \nmid c$ 時無解 ---- ### 通解有解，則有無限多組解 $\{(x, y) + \frac k{\gcd(a,\, b)}(b,\, -a)\,|\, k \in \mathbb Z\}$ 為通解 Note: 可以把 $ax + by = c$ 想成 $(a, b) \cdot (x, y) = c$ 當求出一組 (x, y) 後，再加上跟 (a, b) 垂直的向量不會影響內積結果也就是跟 (b,\, -a) 平行的向量 ---- ### 通解 \begin{align} & \{(x, y) + k(\frac b{\gcd(a,\, b)},\, \frac{-a}{\gcd(a,\, b)})\,|\, k \in \mathbb Z\} \\ =\, &\{(x, y) + k(\frac {\text{lcm}(a,\, b)}a,\, \frac{\text{lcm}(a,\, b)}{-b})\,|\, k \in \mathbb Z\} \\ \end{align} Note: $ab = \gcd(a, b)\text{lcm}(a, b)$ ---- ### 通解有無限多組解就有爆 long long 的風險但上面介紹的實作法可以保證 $|x| \le b,\, |y| \le a$ ---- ### Example $16x + 10y = 2$ 有一組解 $(x, y) = (2, -3)$ 有通解 $\{(2, -3) + k(\frac {80}{16},\, \frac{80}{-10})\,|\, k \in \mathbb Z\}$ 也就是 $(2 + 5k, -3-8k)$ ---- ### 練習題 - [uva 10104 - Euclid Problem](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1045) - [uva 12775 - Gift Dilemma](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4628) --- ## 模逆元 ---- ### 學習動機一般競賽題目中 通常會將答案 $\bmod$ 一數若想在同餘系統下做出基本的四則運算必須得學習如何在 $\bmod$ 一數時做除法 ---- ### 除法 **除法** 是乘法的反運算除以 $a$ 等同於 乘上一個 $a$ 的**乘法反元素** ---- ### 模反元素在一個模底下的乘法反元素 稱為**模反元素**(**模逆元**)，記作 $a^{-1}$ $ab \equiv 1 \quad (\text{mod}\ m)$ $a^{-1} \equiv b \quad (\text{mod}\ m)$ Note: 如果找得到模逆元則可以做除法 ---- ### 存在性求解 $ax \equiv 1 \pmod m$ 等價於求解 $ax + my = 1$ $x$ 即為 $\text{a}$ 的模逆元 根據 $\text{extgcd}$ 裡的 [定理 $2$](#/8/3) $\gcd(a, m) = 1$ 有整數解 Note: 解釋為何等價由此可知，$a$ 在模 $m$ 底下存在模逆元，若且唯若 $\gcd(a, m) = 1$ 也就是二數必須互質 ---- ### Example $7 \cdot 43 \equiv 301 \equiv 1 \pmod{60}$ 稱 $43$ 是 $7$ 的模逆元 記作 $7^{-1}$ $21 \cdot 7^{-1} \equiv 21 \cdot 43 \equiv 903 \equiv 3 \pmod {60}$ ---- ### 擴展歐幾里得算法 $ax \equiv 1 \enspace\pmod m$ $\exists\, y \in \mathbb Z,\, ax + my = 1$ ---- ### 歐拉定理 \begin{equation} a^{\phi(n)} \equiv 1\pmod n \\ \Rightarrow a^{\phi(n)-1} \equiv a^{-1} \pmod n \end{equation} e.g. $7^{\phi(60) - 1} \equiv 7^{15} \equiv 43\pmod{60}$ ---- ### 線性表格當模數是質數時 有一演算法可以做到線性建立模逆元表格 ---- ### 定理 $\text{inv}[i] = -\Big\lfloor\frac{m}{i}\Big\rfloor \,\text{inv}[m\bmod i] \bmod m$ $\text{if } m \text{ is prime}$ ---- ### 實作 ```cpp= inv[1] = 1; for(int i = 2; i < m; ++i) inv[i] = (m - (m/i) * inv[m%i] % m) % m; ``` 上述演算法也可以改成 $O(N)$ 求 $1\sim N$， ---- ### 實作直接遞迴 ```cpp= int inv(int i) { return (i == 1) ? 1 : (m - (m/i) * inv(m%i) % m) % m; } ``` ---- ### 練習題 - [Zerojudge a289](https://zerojudge.tw/ShowProblem?problemid=a289) --- ## 快速冪 Multiply-and-Square Algorithm ---- ### 前言此算法用於快速計算 $a^b \bmod c$ 其核心精神在於不要浪費曾經算過的東西 ---- ### 想法 $b = \lfloor \frac{b}{2} \rfloor \times 2 + (b\bmod 2)$ $a^b = a^{\lfloor \frac{b}{2} \rfloor} \times a^{\lfloor \frac{b}{2} \rfloor} \times a^{(b\bmod 2)}$ 這使得我們可以用**遞迴**的方式實作快速冪 ---- ### 遞迴實作 ```cpp= [|2|4|5|7-8|7|8] int qp(int a, int b, int c) { if (b == 0) return 1; int x = qp(a, b >> 1, c); int y = x * x % c; if (b & 1) return y * a % c; else return y; } ``` Note: | Line | 說明 | | ---- | ---------------------------------------------------------------------------------------------------------------------------------------- | | 1-9 | 將 $a^b$ 分成 $\left(a^{\left(\frac{b}{2}\right)}\right)^2$，遞迴計算並合併。 | | 4 | 遞迴算出 $x = a^{\left\lfloor \frac{b}{2} \right\rfloor}$ | | 5 | 合併 $y = x^2 = a^{2\left\lfloor \frac{b}{2} \right\rfloor}$ | | 6-7 | 若 $b$ 是偶數則 $b = {2\left\lfloor \frac{b}{2} \right\rfloor}$ 否則 $b = {2\left\lfloor \frac{b}{2} \right\rfloor} + 1$，需要補乘 $1$ 個 $a$ | ---- ### 複雜度 $\text{O}(\log b)$ Note: $b$ 不斷折半 ---- ### 瘋狂平方法想像一下，我們可以如何快速地增加 $a$ 的次方 $a,\,a^2,\,a^4,\,a^8,\,a^{16},\,\cdots$ ---- ### 組裝 $a,\,a^2,\,a^4,\,a^8,\,a^{16},\,\cdots$ How to compute $a^b$ efficiently? $a^{21} = a^{16\,+\,4\,+\,1} = a^{16} \cdot a^4 \cdot a^1$ ---- ### 二進位我們常用的是十進位 $21 = 16\,+\,4\,+\,1$ 程式中常用的是二進位 $21_{(10)} = 10101_{(2)}$ Note: 1, 10, 100, 1000, ... 1, 2, 4, 8, ... 只要會實作二進位，就能好好實作快速冪 ---- ### 觀察 $21_{(10)} = 10101_{(2)}$ $18_{(10)} = 10010_{(2)}$ $21$ 是奇數二進位最低位是 $1$ $18$ 是偶數二進位最低位是 $0$ Note: 其實很合理，二進位其他位代表的都是偶數 ---- ### 觀察 $21_{(10)} = 10101_{(2)}$ $10_{(10)} = 01010_{(2)}$ $\big\lfloor\frac{21}2\big\rfloor = 10$ 相當於每一位往最低位移一位 Note: 8, 4, 2, 1 -> 4, 2, 1, 0 ---- ### 想法想像你有一個數字 $b$ 用奇偶性來看最後一位 再用 ```b / 2``` 來往最低位吃掉一位 ----  ### Example \begin{align} 13_{(10)} &= 1101_{(2)} \\ 6_{(10)} &= 0110_{(2)} \\ 3_{(10)} &= 0011_{(2)} \\ 1_{(10)} &= 0001_{(2)} \\ 0_{(10)} &= 0000_{(2)} \end{align} ----  ### Example \begin{align} 13_{(10)} &\to 1 \\ 6_{(10)} &\to 0 \\ 3_{(10)} &\to 1 \\ 1_{(10)} &\to 1 \\ 0_{(10)} &\to \text{finish} \end{align} ----  ### Example \begin{align} a \to\ &13& &6& &3& &1& \\ a\, \&\, 1 \to\ &1& &0& &1& &1& \\ 2^k \to\ &1& &2& &4& &8& \\ 13 = \ &1& +\ &0& +\ &4& +\ &8& \end{align} ---- ### 實作 ```cpp= [|2|3|4] void binary(int b) { while (b != 0) { cout << (b & 1); b >>= 1; } } ``` ---- ### 實作 ```cpp= [|1|2|3-8|3|4-5|5|7|6|9] int qp(int a, int b, int c) { int ans = 1; while (b != 0) { if (b & 1) ans = ans * a % c; a = a * a % c; b >>= 1; } return ans; } ``` Note: | Line | 說明 | | ------- | --------------------------- | | 3 | 先mod沒差，避免後續運算溢位 | | 4、5、7 | 觀察 $b$ 的二進位 | | 6 | 列舉 $a^1\ a^2\ a^4\ ...$ | ---- ### 複雜度 $\text{O}(\log b)$ Note: $b$ 的二進位只有約 $\log b$ 位 ---- ### 練習題 - [TIOJ 2095 快速冪（駭客題）](https://tioj.ck.tp.edu.tw/problems/2095) - [toj 36 simple problem](https://toj.tfcis.org/oj/pro/36/) --- ## 質數測試 ---- ### 需求篩法可區分出一段範圍內的質數但只能做到 $[1,\, 5 \times 10^7]$ 的範圍那麼檢驗一數是不是質數能做到多快呢? ---- ### $\sqrt N$ test 直接檢查它有沒有除了 $1$ 和自身以外的因數 ---- ### 複習費馬小定理 $a^{p-1} \equiv 1 \pmod p,\ p \text{ is a prime}$ e.g. $4^{16} \equiv 1 \pmod {17}$ ---- ### 引理 1 $a^2 \equiv 1 \enspace\Leftrightarrow\enspace a \equiv \pm 1 \pmod p,\ p \text{ is a prime}$ \begin{align} \Rightarrow&\, p \mid (a^2 - 1) \\ \Rightarrow&\, p \mid (a - 1) \text{ or } p \mid (a + 1) \\ \Rightarrow&\, a \equiv \pm 1 \pmod p \end{align} ---- ### Miller Rabin 隨便挑一個 $a$ 看看它是否通過了這兩個性質的考驗 * 如果沒通過，那麼它就是合數。 * 如果通過了，代表它有 $75\%$ 的可能性是質數。 ---- ### 方法 $a^{p-1},\, a^{\frac{p-1}{2}},\, a^{\frac{p-1}{4}},\, \dots, a^d \pmod p$ 根據費馬小定理 第一項是 $1$ 根據引理 $1$ 不斷開平方根 只能開出 $1$ or $-1$ ---- ### 可能的結果 $1,\, 1,\, \dots,\, 1,\, -1,\, ?,\,\dots$ or $1,\, 1,\, \dots,\, 1,\, 1$ Note: $d \text{ is odd}$ 1. 此數列中至少開出一平方根為 $-1$ 2. 或者整個數列全是 $1$，或者說 $a^d = 1$。 ---- ### Example $a = 4,\, p = 13$ $4^{13 - 1},\, 4^6,\, 4^3\, \equiv\, 1,\, 1,\, -1 \pmod {13}$ Note: 質數一定對對了不一定是質數 ---- ### Example $a = 4,\, p = 21$ $4^{21 - 1},\, 4^{10},\, 4^5\, \equiv\, 16,\, 4,\, 16 \pmod {21}$ Note: 質數一定對對了不一定是質數 ---- ### Note $p$ 是質數 $\Rightarrow$ 性質會成立性質不成立 $\Rightarrow$ $p$ 是合數性質成立 $\not\Rightarrow$ $p$ 是質數 ---- ### 反例 $a = 174,\, p = 221$ $174^{221 - 1},\, 174^{110},\, 174^{55}\, \equiv\, 1,\, -1,\, 47 \pmod {221}$ 但 $221 = 13 \cdot 17$ Note: 質數一定對對了不一定是質數 ---- ### 做法 * 反著構造此數列 如果 $a^d=1\text{ or } -1$ 則未來必定通過**費馬測試** * 若不等於，則後續出現 $-1$ 也可以通過測試 但出現 $1$ 會使**方根測試**失敗 ---- ### 實作 ```cpp= [|1|2-3|5-7|5|7|9-11|13-17|13|14|15|16|18] bool miller_rabin(int n, int a) { if ((n & 1) == 0) return n == 2; int u = n - 1, t = 0; while ((u & 1) == 0) u >>= 1, ++t; int x = qp(a, u, n); if (x == 1 || x == n - 1) return true; for (int i = 0; i < t - 1; ++i) { x = mul(x, x, n); if (x == 1) return false; if (x == n - 1) return true; } return false; } ``` Note: 5-7 分解次方 9-11 檢查 a^u 13 算冪次剩下的部分，最後一次不用算 15 方根測試失敗 16 偷窺未來 18 最後還沒成功就是失敗 ---- ### 複雜度單個 $a$ 測試是 $\text{O}(\log n)$ ---- ### 小結 * 這演算法不保證正確性 但隨機用多個 $a$ 測試的話 其正確性是頗高的 * 取 $a = 2, 7, 61$ 可以準確判定 int 範圍內的數 * 取 $a$ 小於 $40$ 的所有質數 可以準確判定 long long 範圍內的數 ---- ### 練習題 - [Zerojudge a007 判斷質數](https://zerojudge.tw/ShowProblem?problemid=a007) --- ## 中國剩餘定理 ---- ### 用途求解一元一次同餘聯立方程式 \begin{equation} \begin{cases} x \equiv a_1 & \pmod {p_1}\\ x \equiv a_2 & \pmod {p_2}\\ ...\\ x \equiv a_n & \pmod {p_n}\\ \end{cases} \end{equation} \begin{equation} \forall i, j \enspace \text{gcd}(p_i, p_j) = 1 \end{equation} ---- ### 定理 \begin{equation} x \equiv \displaystyle\sum^n_{k=1}a_k\, M_k\, m_k \pmod N \end{equation} $N = \displaystyle\prod_{i=1}^n p_i\, ,\ M_k = \frac{N}{p_k}\, ,\ M_k\, m_k \equiv 1\, \pmod {p_k}$ Note: 簡單來說，我們有一個未知數 $x$ 跟數條同餘式子欲合併成單條 $x$ 的同餘式 - 證明 > 此答案為構造解，可自行代入每一條式子進行驗證 ---- ### Example \begin{equation} \begin{cases} x \equiv 1 & \pmod {3}\\ x \equiv 4 & \pmod {5}\\ x \equiv 3 & \pmod {7}\\ \end{cases} \end{equation} \begin{align} x &\equiv 1 \cdot 35 \cdot 2 + 4 \cdot 21 \cdot 1 + 3 \cdot 15 \cdot 1 \\ &\equiv 94 \pmod{105} \end{align} ---- ### 求解程式實作時可以慢慢將式子兩兩合併 \begin{equation} \begin{cases} x \equiv a_1 & \pmod {p_1} \\ x \equiv a_2 & \pmod {p_2} \\ \end{cases} \end{equation} $p_1x + p_2y = 1$ $x \equiv a_1 \cdot p_2y + a_2 \cdot p_1x \pmod{p_1 \cdot p_2}$ ---- ### 實作 ```cpp= [|1-3|5|7|8|9] struct modEq { int a, p; // x \equiv a \pmod p }; modEq merge(modEq e1, modEq e2) { int a, p, x, y; extgcd(e1.p, e2.p, x, y); p = e1.p * e2.p; a = e1.a * e2.p * y + e2.a * e1.p * x; return (modEq){a, p}; } ``` ---- ### 擴展如果模的數兩兩之間沒有互質呢? ---- ### Example \begin{equation} x \equiv 5 \quad \pmod 6 \Leftrightarrow \begin{cases} x \equiv 1 \quad \pmod 2 \\ x \equiv 2 \quad \pmod 3 \end{cases} \end{equation} ---- ### Example \begin{equation} x \equiv 10 \quad \pmod {50} \Leftrightarrow \begin{cases} x \equiv 0 \quad \pmod 2 \\ x \equiv 10 \quad \pmod{5^2} \end{cases} \end{equation} ---- ### Example \begin{equation} x \equiv 123 \quad \pmod {360} \Leftrightarrow \begin{cases} x \equiv 3 \quad \pmod {2^3} \\ x \equiv 6 \quad \pmod {3^2} \\ x \equiv 3 \quad \pmod 5 \end{cases} \end{equation} ---- ### 小結技巧性地先拆開再合併迴避掉 $\gcd(b_i, b_j) \neq 1$的問題合併時順便檢查是否有不合理之處 \begin{cases} x \equiv 3 \quad \pmod 5 \\ x \equiv 10 \quad \pmod {5^2} \end{cases} ---- ### 擴展歐幾里得算法 \begin{cases} x \equiv r_1 \quad \pmod {m_1} \\ x \equiv r_2 \quad \pmod {m_2} \end{cases} $x = m_1p + r_1 = m_2q + r_2$ 移項得 $m_1p+m_2(-q) = r_2 - r_1$ 利用擴展歐基里德算法可在 $\text{O}(\ \log(\max\{m_1, m_2\} \ )$ 找出一組 $(p, q)$ ---- ### 擴展歐幾里得算法 $l = \text{lcm}(m_1, m_2)$ [解的通式](#/8/14) 為 $(p', q') = (p + \frac l {m_1}k, q - \frac l {m_2}k)$ $x = m_1p' + r_1 = m_1p + lk+r_1$ $\Rightarrow x \equiv m_1p + r_1 \pmod l$ ---- ### 無解若方程無解，則代表出現矛盾的狀況 ---- ### Example \begin{cases} x \equiv 5 \quad \pmod {6} \\ x \equiv 8 \quad \pmod {9} \end{cases} $6p + 9(-q) = 8 - 5 = 3$ $(p, q) = (-1, -1)$ $x \equiv 6p + 5 \equiv 17 \pmod{18}$ ---- ### Example \begin{cases} x \equiv 5 \quad \pmod {6} \\ x \equiv 6 \quad \pmod {9} \end{cases} $6p + 9(-q) = 6 - 5 = 1$ $(p, q)$ 無解 ---- ### 練習題 - [Luogu P1516 青蛙的約會](https://www.luogu.com.cn/problem/P1516) - [toj 210 寧寧數貓咪](https://toj.tfcis.org/oj/pro/210/)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.