# 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$ 的最大正整數。 :::info 考慮 $\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)$ 最重要的性質，我們熟悉的輾轉相除法的根據。 <font size="2"> Note: 「%」取餘數</font> --- ### 複習：輾轉相除法 別名：歐幾里德演算法 $$ \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)$ <font color="red"> 我們可以從輾轉相除法的過程找到靈感</font> --- #### 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 的整數倍和。 <font color="red"> $\therefore 18$ 可成功分解成 A,B 的整數倍和。</font> --- | 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 | <font size="5">$6 = 1 \cdot (1 \cdot 786+ -4 \cdot 186)+ -2 \cdot (1 \cdot 186+ -4 \cdot (1 \cdot 786+ -4 \cdot 186))$ </font> | | 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 | <font size="6"> 講到這裡，我想這個表格就可以足夠引導各位自行完成演算法，在學習的演算法時，有時候了解核心思路之後自己寫出來，會很有成就感，也會具有更靈活運用的能力。 解題思路上面有點類似動態規劃：</font><font color="red">「小事化了、大事化小」</font> --- #### 練習題 [Codeforces 1165 E](https://codeforces.com/contest/1165/problem/E) [Codeforces 1244 C](https://codeforces.com/contest/1244/problem/C) ---  <!-- ## 主題 Modulus Greatest Common Divisor ## 流程 餘數 同餘 加法乘法 最大公因數 擴展歐幾里德 *選讀* 歐拉定理 費馬小定理 ## 例題 CF 1165E CF 1244C  --> <style> .reveal { color: black; } .reveal h3, .reveal h4, .reveal h1{ color: black; } .reveal section img { border: 0px; } body { background-image: url("https://i.imgur.com/yCEc6qJ.png"); background-size: 1920px 1080px; } </style>