Week 14 課程簡報

目標

  • 看懂表示法 \(A\equiv B\) \(\mod{n}\)
  • 暸解「擴展歐幾里得演算法」實作概念。

選讀

  • 模反元素
  • 歐拉定理
  • 費馬小定理

複習：餘數

\[ \begin{aligned} &42 \div 18 = 2 ... 6\\ &60 \div 18 = 3 ... 6\\\\ &42 = 2 \cdot 18 + 6\\ &60 = 3 \cdot 18 + 6 \end{aligned} \]

同餘（Modular arithmetic）

當除以\(18\)的時候，\(42\)與\(60\)的餘數都是\(6\)。

\[ 42 \equiv 60 \mod{18} \]

同餘：加法與乘法可以結合

若
\[ a \equiv b \mod n \\c \equiv d \mod n \]
則
\[ a+c \equiv b+d \mod n\\a\times c \equiv b\times d \mod n \]

最大公因數：定義

能夠整除 \(A,B\) 的最大正整數。

考慮 \(\gcd(A, B) = g\)

  • 兩個參數 \(A,B\) 的定義域為整數\(Z\)，
  • 值域 \(g\) 為自然數\(N\)＆\(0\)

最大公因數：性質1

\(gcd(A, B) = gcd(|A|, |B|)\)
藉由絕對值，我們可以把參數的定義域放大到所有整數。

最大公因數：性質2

\(gcd(A, 0) = |A|\)
可以整除 \(A\) & \(0\) 的正整數就是\(|A|\)。

最大公因數：性質3

\(gcd(A, B) = gcd(A\%B, B)\)
最重要的性質，我們熟悉的輾轉相除法的根據。
Note: 「%」取餘數

複習：輾轉相除法

別名：歐幾里德演算法

\[ \begin{aligned} 78 &\div 66 = 1 ... 12\\ 66 &\div 12 = 5 ... 6\\ 12 &\div 6 = 2 ... 0\\ &\Rightarrow 6 \end{aligned} \]

核心問題

若：\(g = gcd(A, B)\)
尋找一組整數對\((x,y)\)
使得：\(x\cdot A + y \cdot B = g\)

擴展歐幾里得演算法

沒辦法一次到位解決的問題，可以分多次解決

範例：

\(A = 786, B = 186\)，請尋找一組整數對\((x,y)\)
使得 \(x\cdot A + y \cdot B = gcd(A, B)\)

我們可以從輾轉相除法的過程找到靈感

step 1

考慮數列R，為輾轉相除法的過程餘數。

數列R 目標
786
186
42
18
6 \(6 = x\cdot 786+ y \cdot 186\)

step 2

如何分次解決呢？

數列R 目標
786 \(786 = 1\cdot 786+ 0 \cdot 186\)
186 \(186 = 0\cdot 786+ 1 \cdot 186\)
42
18
6 \(6 = x\cdot 786+ y \cdot 186\)

step 3

\(\because 786 \div 186 = 4 ... 42\)
\(\therefore 42 = (1) \cdot 786 + (-4) \cdot 186\)
\(42\)可拆解為 \(786\) & \(186\) 的整數倍和。

數列R 目標
786 \(786 = 1\cdot 786+ 0 \cdot 186\)
186 \(186 = 0\cdot 786+ 1 \cdot 186\)
42 \(42 = 1 \cdot 786+ -4 \cdot 186\)
18
6 \(6 = x\cdot 786+ y \cdot 186\)

step 4

\(\because 186 \div 42 = 4 ... 18\)
\(\therefore 18 = (1) \cdot 186 + (-4) \cdot 42\)
\(18\)可拆解為 \(186\) & \(42\) 的整數倍和。

又 \(\because 42\) 可成功分解成 A,B 的整數倍和。
\(\therefore 18\) 可成功分解成 A,B 的整數倍和。

R 目標
786 \(786 = 1\cdot 786+ 0 \cdot 186\)
186 \(186 = 0\cdot 786+ 1 \cdot 186\)
42 \(42 = 1 \cdot 786+ -4 \cdot 186\)
18 \(18 = 1 \cdot 186+ -4 \cdot (1 \cdot 786+ -4 \cdot 186)\)
6 \(6 = 1 \cdot (1 \cdot 786+ -4 \cdot 186)+ -2 \cdot (1 \cdot 186+ -4 \cdot (1 \cdot 786+ -4 \cdot 186))\)
6 \(6 = 9\cdot 786+ (-38) \cdot 186\)

結論

R 786 168 42 18 6
X 1 0 1 -4 9
Y 0 1 -4 17 -38

講到這裡，我想這個表格就可以足夠引導各位自行完成演算法，在學習的演算法時，有時候了解核心思路之後自己寫出來，會很有成就感，也會具有更靈活運用的能力。

解題思路上面有點類似動態規劃：「小事化了、大事化小」

練習題

Codeforces 1165 E
Codeforces 1244 C

Select a repo