# Week 14 課程簡報
---
![](https://i.imgur.com/Jtb6sPL.png)
---
### 目標
- 看懂表示法 $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)
---
![](https://i.imgur.com/Za4tJEZ.png)
<!--
## 主題
Modulus
Greatest Common Divisor
## 流程
餘數
同餘 加法乘法
最大公因數
擴展歐幾里德
*選讀*
歐拉定理
費馬小定理
## 例題
CF 1165E
CF 1244C
![](https://i.imgur.com/yCEc6qJ.png)
-->
<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>
{"metaMigratedAt":"2023-06-15T08:56:32.508Z","metaMigratedFrom":"YAML","title":"Week 14 課程簡報","breaks":"true","contributors":"[{\"id\":\"22f9b133-722f-450f-8c0a-ffea0dacb892\",\"add\":4825,\"del\":752}]"}