108 年 國立中山大學資訊工程學系碩士班甲組《離散數學與演算法》

核心觀念

本題屬於離散數學中「組合計數」（Combinatorics）的經典應用題，主要考驗考生對以下基本定義與原理的理解與運用：

1. 組合公式（Combination Formula）：從 $n$ 個相異物件中不考慮順序取出 $k$ 個物件的方法數記作 $\binom{n}{k}$ 或 $C(n,k)$，其定義為：
   $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
   且具備對稱性質：$\binom{n}{k} = \binom{n}{n-k}$。

2. 乘法原理（Multiplication Principle）：若完成某個任務需分為若干個相續的獨立步驟，且第一步驟有 $m$ 種方法、第二步驟有 $n$ 種方法，則完成整項任務的方法數為 $m \times n$。

3. 加法原理（Addition Principle）：若完成某個任務可以透過若干個彼此互斥（Mutually Exclusive）的情境或分類來達成，則總方法數為各情境方法數之和。

---

解題方法

本題設定共有 10 名男性與 10 名女性（合計 20 人），需選出 14 人組成委員會。

(a) 恰選出 7 名男性與 7 名女性

此挑選過程可分為兩個獨立選擇步驟：

1. 選男性：從 10 名男性中選出 7 名，方法數為 $\binom{10}{7}$。
   利用對稱性計算：
   $\binom{10}{7} = \binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$
2. 選女性：從 10 名女性中選出 7 名，方法數為 $\binom{10}{7}$。
   同理可得：
   $\binom{10}{7} = 120$

依據乘法原理，同時選出 7 男 7 女之總選擇方法數為：
$\text{總方法數} = \binom{10}{7} \times \binom{10}{7} = 120 \times 120 = 14400$

(b) 至少選出 8 名男性

委員會總人數固定為 14 人。設選出的男性人數為 $k$，因為要求「至少 8 名男性」且男性總數只有 10 人，故 $k$ 的可能取值為 $8, 9, 10$。相對應的女性人數即為 $14 - k$ 人。

依據男性人數進行互斥分類討論：

1. 情境一：選出 8 名男性與 6 名女性 ($k = 8$)
   • 從 10 名男性選 8 人的方法數：$\binom{10}{8} = \binom{10}{2} = \frac{10 \times 9}{2 \times 1} = 45$

核心觀念

本題考查命題邏輯中的：

• 雙條件命題：$p \leftrightarrow q$ 表示 $p$ 與 $q$ 真值相同，且等價於
  $p \leftrightarrow q \equiv (p \rightarrow q)\wedge(q\rightarrow p)$
• 蘊涵命題的傳遞性：
  $(p\rightarrow q)\wedge(q\rightarrow r)\Rightarrow(p\rightarrow r)$
• 命題等價的證明：證明左右兩邊可以互相推出。

令

$$A=(r\leftrightarrow p)\wedge(p\leftrightarrow q)\wedge(q\leftrightarrow r)$$ $$B=(r\rightarrow p)\wedge(p\rightarrow q)\wedge(q\rightarrow r)$$

題目要求證明 $A\leftrightarrow B$ 為永真命題。

解題方法

採用「雙向蘊涵」證明法，分別證明：

$$A\Rightarrow B$$

以及

$$B\Rightarrow A$$

如此即可得到 $A\leftrightarrow B$。

證明 $A\Rightarrow B$

由雙條件命題的定義：

$$r\leftrightarrow p\Rightarrow r\rightarrow p$$ $$p\leftrightarrow q\Rightarrow p\rightarrow q$$ $$q\leftrightarrow r\Rightarrow q\rightarrow r$$

因此，若

$$(r\leftrightarrow p)\wedge(p\leftrightarrow q)\wedge(q\leftrightarrow r)$$

為真，則三個蘊涵命題必定同時為真：

$$(r\rightarrow p)\wedge(p\rightarrow q)\wedge(q\rightarrow r)$$

所以：

$$A\Rightarrow B$$

證明 $B\Rightarrow A$

已知：

$$r\rightarrow p,\qquad p\rightarrow q,\qquad q\rightarrow r$$

要證明三個雙條件命題，必須補出各自的反向蘊涵。

證明 $r\leftrightarrow p$

已知 $r\rightarrow p$。

另一方面，由

$$p\rightarrow q,\qquad q\rightarrow r$$

利用蘊涵的傳遞性可得：

$$p\rightarrow r$$

因此：

$$(r\rightarrow p)\wedge(p\rightarrow r)$$

也就是：

$$r\leftrightarrow p$$

證明 $p\leftrightarrow q$

核心觀念

嚴格子集 $A\subset B$ 包含兩個條件：

1. $A$ 中每個元素都屬於 $B$，即 $A\subseteq B$。
2. $B$ 至少有一個元素不屬於 $A$，即 $A\ne B$。

因此：

$$A\subset B \iff \left(\forall x\in \bar U,\ x\in A\Rightarrow x\in B\right) \land \left(\exists x\in \bar U,\ x\in B\land x\notin A\right)$$

---

解題方法

(a) 表示 $A\subset B$

依照嚴格子集的定義，答案為：

$$\boxed{ \left(\forall x\in \bar U,\ x\in A\Rightarrow x\in B\right) \land \left(\exists x\in \bar U,\ x\in B\land x\notin A\right) }$$

第一部分表示 $A$ 沒有任何元素超出 $B$；第二部分表示 $B$ 至少包含一個 $A$ 沒有的元素，因此兩集合不相等。

---

(b) 否定 $A\subset B$

將 (a) 的命題整體否定：

$$\neg(P\land Q)\equiv \neg P\lor\neg Q$$

其中

$$P=\forall x\in\bar U,\ x\in A\Rightarrow x\in B$$

其否定為：

$$\neg P \equiv \exists x\in\bar U,\ x\in A\land x\notin B$$

這表示 $A$ 至少有一個元素不在 $B$ 中，也就是 $A\not\subseteq B$。

另一部分為：

$$Q=\exists x\in\bar U,\ x\in B\land x\notin A$$

其否定為：

$$\neg Q \equiv \forall x\in\bar U,\ x\notin B\lor x\in A$$

等價於：

$$\forall x\in\bar U,\ x\in B\Rightarrow x\in A$$

核心觀念

嚴格子集 $A\subset B$ 包含兩個條件：

1. $A$ 中每個元素都屬於 $B$，即 $A\subseteq B$。
2. $B$ 至少有一個元素不屬於 $A$，即 $A\ne B$。

因此：

$$A\subset B \iff \left(\forall x\in \bar U,\ x\in A\Rightarrow x\in B\right) \land \left(\exists x\in \bar U,\ x\in B\land x\notin A\right)$$

---

解題方法

(a) 表示 $A\subset B$

依照嚴格子集的定義，答案為：

$$\boxed{ \left(\forall x\in \bar U,\ x\in A\Rightarrow x\in B\right) \land \left(\exists x\in \bar U,\ x\in B\land x\notin A\right) }$$

第一部分表示 $A$ 沒有任何元素超出 $B$；第二部分表示 $B$ 至少包含一個 $A$ 沒有的元素，因此兩集合不相等。

---

(b) 否定 $A\subset B$

將 (a) 的命題整體否定：

$$\neg(P\land Q)\equiv \neg P\lor\neg Q$$

其中

$$P=\forall x\in\bar U,\ x\in A\Rightarrow x\in B$$

其否定為：

$$\neg P \equiv \exists x\in\bar U,\ x\in A\land x\notin B$$

這表示 $A$ 至少有一個元素不在 $B$ 中，也就是 $A\not\subseteq B$。

另一部分為：

$$Q=\exists x\in\bar U,\ x\in B\land x\notin A$$

其否定為：

$$\neg Q \equiv \forall x\in\bar U,\ x\notin B\lor x\in A$$

等價於：

$$\forall x\in\bar U,\ x\in B\Rightarrow x\in A$$

核心觀念

本題屬於組合數學（Combinatorics）中的格網計數問題（Grid Counting Problem），核心原理為：

1. 乘法原理（Rule of Product）：若一項操作可分為兩個獨立的步驟進行，第一步驟有 $a$ 種選法，第二步驟有 $b$ 種選法，則完成該操作共有 $a \times b$ 種不同的方法。
2. 一維連續區間選擇（Subsegment Selection）：在長度為 $n$ 個單元格的直線區域中，選擇長度為 $k$ 的連續區間，其可移動的起始位置共有 $(n - k + 1)$ 種選法。

---

解題方法

(a) 推導與計算

要求在 $9 \times 9$ 的棋盤中尋找 $3 \times 3$ 正方形的數量：

1. 水平方向起始位置選擇：
   $9 \times 9$ 棋盤在水平方向由 $9$ 個 $1 \times 1$ 的單元格組成。若要容納長度為 $3$ 的區塊，該區塊的左邊界（起始單元格）可以落在第 $1, 2, 3, 4, 5, 6, 7$ 個單元格。
   水平方向的可能位置數為：
   $9 - 3 + 1 = 7$

2. 垂直方向起始位置選擇：
   同理，垂直方向由 $9$ 個 $1 \times 1$ 的單元格組成。要容納長度為 $3$ 的區塊，該區塊的上邊界（起始單元格）可以落在第 $1, 2, 3, 4, 5, 6, 7$ 個單元格。
   垂直方向的可能位置數為：
   $9 - 3 + 1 = 7$

3. 計算總數：
   一個 $3 \times 3$ 的正方形由其「左上角頂點」唯一確定。根據乘法原理，水平方向與垂直方向的選擇互相獨立，故 $3 \times 3$ 正方形的總數為：
   $7 \times 7 = 7^2 = 49$

---

(b) 推導與計算

考慮一般化情況：在 $n \times n$ 的棋盤中，計算 $k \times k$ 正方形的數量（其中 $1 \le k \le n$）：

1. 水平方向起始位置選擇：
   棋盤水平方向包含 $n$ 個 $1 \times 1$ 的單元格。長度為 $k$ 的邊在水平方向上可放置的起始位置為第 $1$ 格至第 $(n - k + 1)$ 格。
   水平方向共有 $(n - k + 1)$ 種可能選擇。

2. 垂直方向起始位置選擇：
   棋盤垂直方向包含 $n$ 個 $1 \times 1$ 的單元格。長度為 $k$ 的邊在垂直方向上可放置的起始位置為第 $1$ 格至第 $(n - k + 1)$ 格。

核心觀念

本題考查的核心知識為離散數學中的鴿籠原理（Pigeonhole Principle，又稱鴿巢原理）與集合子集計數（Subset Counting）。

• 鴿籠原理（Pigeonhole Principle）：若將 $n$ 個物件（鴿子）放入 $m$ 個容器（鴿籠）中，且 $n > m$，則至少有一個容器包含至少 2 個物件。
• 子集計數與元素和邊界：對於大小為 $n$ 的有限集合 $S$，包含 $k$ 個元素的子集個數為組合數 $\binom{n}{k}$。取子集元素和的最大可能值時，由集合中可能出現的最大元素決定。

---

解題方法

本題採用鴿籠原理進行嚴密證明。證明關鍵在於構造一個合適的子集家族（鴿子），使其數量嚴格大於該家族子集元素和可能取值的範圍總數（鴿籠），從而導出必有至少兩個相異子集具備相同的元素和。

證明推導步驟如下：

1. 設定變數與範圍：
   設 $S = \{a_1, a_2, a_3, a_4, a_5\}$ 為包含 5 個正整數的集合。因為 $S$ 中元素互異且最大值不超過 9，可將其從小到大排列為：
   $1 \le a_1 < a_2 < a_3 < a_4 < a_5 \le 9$

2. 計算鴿子數量（選取特定大小的子集家族）：
   考慮 $S$ 中所有大小為 1、2 或 3 的非空子集所構成的集合家族 $\mathcal{F}$：
   $\mathcal{F} = \{ A \subseteq S : 1 \le |A| \le 3 \}$
   計算家族 $\mathcal{F}$ 中子集的總個數：
   $|\mathcal{F}| = \binom{5}{1} + \binom{5}{2} + \binom{5}{3} = 5 + 10 + 10 = 25$
   因此，共有 $25$ 個子集作為「鴿子」。

3. 計算鴿籠數量（確定子集元素和的可能範圍）：
   設 $S(A)$ 表示子集 $A$ 中所有元素的和。

   • 最小可能和：因為 $a_i \ge 1$，對任意非空子集 $A \in \mathcal{F}$，其元素和最小值滿足：
     $S(A) \ge a_1 \ge 1$
   • 最大可能和：因為 $A$ 的元素個數最多為 3（即 $|A| \le 3$），且 $S$ 中最大的三個元素滿足 $a_3 \le 7, a_4 \le 8, a_5 \le 9$，故 $A$ 的元素和最大值滿足：
     $S(A) \le a_3 + a_4 + a_5 \le 7 + 8 + 9 = 24$

核心觀念

本題考查離散數學與數論（Number Theory）中極為核心的兩個同餘定理：費馬小定理（Fermat's Little Theorem）與歐拉定理（Euler's Totient Theorem）。解題時需運用以下核心定義與定理：

1. 同餘（Congruence）：
   對整數 $a, b$ 及正整數 $n$，若 $n \mid (a - b)$，則稱 $a \equiv b \pmod{n}$。
2. 歐拉總體函數（Euler's Totient Function, $\phi(n)$）：
   定義 $\phi(n)$ 為小於等於 $n$ 且與 $n$ 互質的正整數個數。若 $p$ 為質數，則 $\phi(p) = p - 1$。
3. 簡化剩餘系（Reduced Residue System, RRS）：
   模 $n$ 的簡化剩餘系為包含 $\phi(n)$ 個整數的集合 $R = \{r_1, r_2, \dots, r_{\phi(n)}\}$，滿足：
   • 對所有 $1 \le i \le \phi(n)$，$\gcd(r_i, n) = 1$。
   • 若 $i \neq j$，則 $r_i \not\equiv r_j \pmod{n}$。
4. 同餘消去律（Cancellation Law of Congruence）：
   若 $a c \equiv b c \pmod{n}$ 且 $\gcd(c, n) = 1$，則 $a \equiv b \pmod{n}$。

---

解題方法與推導

(a) 證明 Fermat's Theorem：若 $p$ 為質數，對所有 $a \in \mathbb{Z}$， $a^p \equiv a \pmod{p}$

切入點說明：採用「簡化剩餘系同餘乘積法」。先將 $a$ 分為被 $p$ 整除與不被 $p$ 整除兩種狀況討論，利用兩兩不同餘的性質構造同餘重排。

完整推導步驟：

1. 分情況討論 $p \mid a$ 與 $p \nmid a$

• 情況一：若 $p \mid a$
  表示 $a \equiv 0 \pmod{p}$。
  此時 $a^p \equiv 0^p \equiv 0 \equiv a \pmod{p}$，定理顯然成立。

• 情況二：若 $p \nmid a$
  因為 $p$ 為質數且 $p \nmid a$，故 $\gcd(a, p) = 1$。
  考慮模 $p$ 的完全簡化剩餘系集合 $S = \{1, 2, 3, \dots, p-1\}$。
  將 $S$ 中的每個元素皆乘以 $a$，構造新集合：
  $a S = \{a \cdot 1, a \cdot 2, a \cdot 3, \dots, a \cdot (p-1)\}$

2. 證明 $a S$ 模 $p$ 後的元素兩兩不同餘且皆不為 0

• 對任意 $1 \le i \le p-1$，因為 $\gcd(a, p) = 1$ 且 $\gcd(i, p) = 1$，故 $\gcd(a \cdot i, p) = 1$，即 $a \cdot i \not\equiv 0 \pmod{p}$。
• 若存在 $1 \le i < j \le p-1$ 使得 $a \cdot i \equiv a \cdot j \pmod{p}$：
  由於 $\gcd(a, p) = 1$，根據同餘消去律，等式兩邊同除以 $a$ 可得 $i \equiv j \pmod{p}$。這與 $1 \le i < j \le p-1$ 的假設矛盾。

因此，$a S$ 模 $p$ 之後的 $p-1$ 個餘數正好是集合 $S = \{1, 2, \dots, p-1\}$ 中所有元素的一個重排（Permutation）。

3. 相乘並導出結論

將 $a S$ 中所有元素相乘，其模 $p$ 的結果必等於 $S$ 中所有元素相乘：
$(a \cdot 1)(a \cdot 2)\cdots(a \cdot (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}$
$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$

因為 $p$ 為質數，由 $1$ 至 $p-1$ 之所有整數均與 $p$ 互質，故乘積 $\gcd((p-1)!, p) = 1$。
應用同餘消去律，將等式兩邊同除以 $(p-1)!$，得到：
$a^{p-1} \equiv 1 \pmod{p}$

等式兩邊同乘以 $a$，可得：
$a^p \equiv a \pmod{p}$

綜合情況一與情況二，對任意 $a \in \mathbb{Z}$，皆有 $a^p \equiv a \pmod{p}$ 成立。 $\blacksquare$

---

(b) 證明 Euler's Theorem：若 $n \in \mathbb{Z}^+, n > 1$，且 $\gcd(a, n) = 1$，則 $a^{\phi(n)} \equiv 1 \pmod{n}$

切入點說明：將 (a) 小題的簡化剩餘系乘積法推廣至一般的正整數模數 $n$。

完整推導步驟：

1. 建立模 $n$ 的簡化剩餘系

設 $R = \{r_1, r_2, \dots, r_{\phi(n)}\}$ 為模 $n$ 的簡化剩餘系，其中每個 $r_i$ 皆滿足 $1 \le r_i < n$ 且 $\gcd(r_i, n) = 1$。
已知 $\gcd(a, n) = 1$，將 $R$ 中的每一個元素皆乘以 $a$，構造新集合：

核心觀念

本題考查分治遞迴關係式（Divide-and-Conquer Recurrence Relations）的解法與漸近分析（Asymptotic Analysis / Big-Oh Notation）。
主要運用的定義與方法如下：

1. 迭代展開法（Iterative Unrolling / Substitution Method）：針對形如 $f(n) = a f\left(\frac{n}{b}\right) + g(n)$ 且定義在 $S = \{b^i \mid i \in \mathbb{N}\}$ 的遞迴式，透過變數變換令 $n = b^k$（即 $k = \log_b n$），逐步展開遞迴關係至基底條件 $f(1)$，再對等比級數求和以得到 $f(n)$ 的封閉形式（Closed Form）。
2. 漸近上界記號（Big-Oh Notation）：由封閉形式中尋找當 $n \to \infty$ 時的主導項（Dominating Term），確定其漸近上界 $f(n) = O(g(n))$。
3. 主定理（Master Theorem）驗算：可用於快速判斷與雙重確認漸近複雜度的正確性。

---

解題方法

(a) 子題推導

給定遞迴關係式：
$f(1) = 5, \quad f(n) = 6f\left(\frac{n}{3}\right) + 6n \quad \text{其中 } n = 3^k, k \in \mathbb{N}$

步驟一：變數代換與迭代展開
令 $n = 3^k$（即 $k = \log_3 n$），將遞迴式改寫為以 $k$ 表示的形式：
$f(3^k) = 6 f(3^{k-1}) + 6 \cdot 3^k$

將 $f(3^{k-1})$ 繼續代入展開：
$f(3^k) = 6 \left[ 6 f(3^{k-2}) + 6 \cdot 3^{k-1} \right] + 6 \cdot 3^k = 6^2 f(3^{k-2}) + 6^2 \cdot 3^{k-1} + 6 \cdot 3^k$

再展開一次：
$f(3^k) = 6^3 f(3^{k-3}) + 6^3 \cdot 3^{k-2} + 6^2 \cdot 3^{k-1} + 6 \cdot 3^k$

推廣至第 $j$ 次展開的一般式：
$f(3^k) = 6^j f(3^{k-j}) + \sum_{i=1}^{j} 6^i \cdot 3^{k-i+1}$

步驟二：代入基底條件求和
當 $j = k$ 時，遞迴項到達基底 $f(3^0) = f(1) = 5$：
$f(3^k) = 6^k f(1) + \sum_{i=1}^{k} 6^i \cdot 3^{k-i+1}$

化簡後方的累加項 $\sum_{i=1}^{k} 6^i \cdot 3^{k-i+1}$：
$\sum_{i=1}^{k} 6^i \cdot 3^{k-i+1} = \sum_{i=1}^{k} (2 \cdot 3)^i \cdot 3^{k-i+1} = \sum_{i=1}^{k} 2^i \cdot 3^i \cdot 3^{k-i+1} = 3^{k+1} \sum_{i=1}^{k} 2^i$

利用等比級數公式 $\sum_{i=1}^{k} 2^i = \frac{2(2^k - 1)}{2 - 1} = 2^{k+1} - 2$：
$3^{k+1} \left(2^{k+1} - 2\right) = 3 \cdot 3^k \left(2 \cdot 2^k - 2\right) = 6 \cdot (2 \cdot 3)^k - 6 \cdot 3^k = 6 \cdot 6^k - 6 \cdot 3^k$

將此結果與 $f(1) = 5$ 代回：
$f(3^k) = 5 \cdot 6^k + 6 \cdot 6^k - 6 \cdot 3^k = 11 \cdot 6^k - 6 \cdot 3^k$

步驟三：將 $k$ 代換回 $n$ 得到封閉形式與 Big-Oh
因為 $n = 3^k$，故 $k = \log_3 n$，且 $6^k = 6^{\log_3 n} = n^{\log_3 6}$：
$f(n) = 11 \cdot 6^{\log_3 n} - 6n = 11 n^{\log_3 6} - 6n$

觀察主導項（因為 $\log_3 6 = 1 + \log_3 2 \approx 1.631 > 1$）：
$f(n) = O(n^{\log_3 6}) \quad \text{或 } O(6^{\log_3 n})$

---

(b) 子題推導

給定遞迴關係式：
$f(1) = 7, \quad f(n) = f\left(\frac{n}{5}\right) + 8 \quad \text{其中 } n = 5^k, k \in \mathbb{N}$

步驟一：變數代換與迭代展開
令 $n = 5^k$（即 $k = \log_5 n$），將遞迴式改寫為：
$f(5^k) = f(5^{k-1}) + 8$

逐步展開：
$f(5^k) = f(5^{k-2}) + 8 + 8 = f(5^{k-2}) + 2 \cdot 8$
$f(5^k) = f(5^{k-3}) + 3 \cdot 8$

核心觀念

1. 歐幾里得演算法（Euclidean Algorithm）
   用於求解兩正整數 $a, b$ 的最大公因數 $\gcd(a, b)$。根據除法原理，$a = q \cdot b + r$（其中 $0 \le r < b$），則：
   $\gcd(a, b) = \gcd(b, r)$
   持續進行帶餘除法，直到餘數為 $0$，此時最後一個非零餘數即為 $\gcd(a, b)$。

2. 貝祖定理（Bézout's Identity）與擴展歐幾里得演算法（Extended Euclidean Algorithm）
   對於任意兩正整數 $a, b$，必然存在整數 $s, t \in \mathbb{Z}$，使得最大公因數可以表示為 $a, b$ 的線性組合：
   $\gcd(a, b) = s \cdot a + t \cdot b$
   透過歐幾里得演算法的「回代法」（Back-Substitution），將除法過程中的餘數反向代換，即可求得整數係數 $s$ 與 $t$。

---

解題方法

本題求解分為兩個核心階段：

1. 求解最大公因數：由大數對小數進行連除法，記錄每一步的商數與餘數，求得最後的非零餘數 $\gcd(a, b)$。
2. 導出線性組合：從最後一個非零餘數的等式出發，逐層將餘數替換為前一步的式子，最終表示為最初兩數 $a$ 與 $b$ 的線性組合。

---

選項分析

(a) 求解 $\gcd(251, 1920)$ 並表示為線性組合

• 第一階段：歐幾里得演算法（正向相除）
  $1920 = 7 \times 251 + 163 \quad \implies \quad 163 = 1920 - 7 \times 251$
  $251 = 1 \times 163 + 88 \quad \implies \quad 88 = 251 - 1 \times 163$
  $163 = 1 \times 88 + 75 \quad \implies \quad 75 = 163 - 1 \times 88$
  $88 = 1 \times 75 + 13 \quad \implies \quad 13 = 88 - 1 \times 75$
  $75 = 5 \times 13 + 10 \quad \implies \quad 10 = 75 - 5 \times 13$
  $13 = 1 \times 10 + 3 \quad \implies \quad 3 = 13 - 1 \times 10$
  $10 = 3 \times 3 + 1 \quad \implies \quad 1 = 10 - 3 \times 3$
  $3 = 3 \times 1 + 0$
  由上述可知，最後一個非零餘數為 $1$，故 $\gcd(251, 1920) = 1$。

• 第二階段：擴展歐幾里得演算法（反向回代）
  $1 = 10 - 3 \times 3$
  $1 = 10 - 3 \times (13 - 10) = 4 \times 10 - 3 \times 13$
  $1 = 4 \times (75 - 5 \times 13) - 3 \times 13 = 4 \times 75 - 23 \times 13$
  $1 = 4 \times 75 - 23 \times (88 - 75) = 27 \times 75 - 23 \times 88$
  $1 = 27 \times (163 - 88) - 23 \times 88 = 27 \times 163 - 50 \times 88$
  $1 = 27 \times 163 - 50 \times (251 - 163) = 77 \times 163 - 50 \times 251$
  $1 = 77 \times (1920 - 7 \times 251) - 50 \times 251 = 77 \times 1920 - 589 \times 251$
  整理得到線性組合為：
  $1 = (-589) \times 251 + 77 \times 1920$

---

(b) 求解 $\gcd(1371, 2587)$ 並表示為線性組合

• 第一階段：歐幾里得演算法（正向相除）
  $2587 = 1 \times 1371 + 1216 \quad \implies \quad 1216 = 2587 - 1 \times 1371$
  $1371 = 1 \times 1216 + 155 \quad \implies \quad 155 = 1371 - 1 \times 1216$
  $1216 = 7 \times 155 + 131 \quad \implies \quad 131 = 1216 - 7 \times 155$
  $155 = 1 \times 131 + 24 \quad \implies \quad 24 = 155 - 1 \times 131$
  $131 = 5 \times 24 + 11 \quad \implies \quad 11 = 131 - 5 \times 24$
  $24 = 2 \times 11 + 2 \quad \implies \quad 2 = 24 - 2 \times 11$
  $11 = 5 \times 2 + 1 \quad \implies \quad 1 = 11 - 5 \times 2$
  $2 = 2 \times 1 + 0$
  由上述可知，最後一個非零餘數為 $1$，故 $\gcd(1371, 2587) = 1$。

• 第二階段：擴展歐幾里得演算法（反向回代）
  $1 = 11 - 5 \times 2$
  $1 = 11 - 5 \times (24 - 2 \times 11) = 11 \times 11 - 5 \times 24$
  $1 = 11 \times (131 - 5 \times 24) - 5 \times 24 = 11 \times 131 - 60 \times 24$

核心觀念

此題考有向加權圖的最短路徑。邊的方向由箭頭決定，不能把有向邊當成雙向邊。Dijkstra 演算法每次選取尚未確定且暫定距離最小的頂點，再沿其出邊更新鄰點距離；本圖邊權皆為正，適用此法。

（a）由頂點 $b$ 出發

圖中與計算相關的有向邊包括 $b\to a$ 權重 $3$、$b\to c$ 權重 $4$、$b\to h$ 權重 $7$、$c\to f$ 權重 $6$、$h\to g$ 權重 $4$。初始化 $d(b)=0$，其他頂點距離為 $\infty$。

確定頂點	更新結果
$b$	$d(a)=3,\ d(c)=4,\ d(h)=7$
$a$	經 $a$ 到 $c$ 的距離為 $3+6=9$，不優於 $4$
$c$	$d(f)=4+6=10$
$h$	$d(g)=7+4=11$；經 $h$ 到 $f$ 的距離為 $7+9=16$，不優於 $10$
$f$	經 $f$ 到 $g$ 的距離為 $10+9=19$，不優於 $11$
$g$	完成

因此，由 $b$ 到其他各頂點的最短距離為：