描述
給定 \(n\) 顆彈珠和兩種盒子，且兩種盒子的花費和容量分別為 \(c_1\)、\(c_2\) 和 \(n_1\)、\(n_2\)，其中 \(n\)、\(c_1\)、\(c_2\)、\(n_1\) 和 \(n_2\) 都是正整數，現在用數量不定的兩種盒子裝彈珠，並且所有盒子都必須裝滿，若能辦到，問在最低花費下，兩種盒子的所需個數為多少。
思路
令 \(p\) 和 \(q\) 分別為兩種盒子所需的數量，則題目可以表述為
\[ \begin{equation} \underset{p, q}{\mathrm{argmin}}\; f(p, q) = c_1 p + c_2 q \end{equation} \]
且 \(p, q \in \mathbb{Z}^{0+}\) 並同時滿足
\[ \begin{equation} n_1 p + n_2 q = n \end{equation} \]
第一層
既然 \(n\) 的上限是 \(20,0000,0000\)，就不浪費篇幅討論暴力解了，直接進入主題。
第二層
式 \((2)\) 顯然為二元一次丟番圖方程式，並且容易想到（？）貝祖等式，貝祖等式的內容為
令 \(a\) 和 \(b\) 為整數且兩者的最大公因數為 \(d\)，則存在整數 \(x\) 和 \(y\) 使得 \(a x + b y = d\)。
據此有
\[ \begin{equation} n_1 p' + n_2 q' = gcd(n_1, n_2) \end{equation} \]
觀察式 \((2)\) 和式 \((3)\)，兩者的不同在於等號右邊分別為 \(n\) 和 \(gcd(n_1, n_2)\)，當 \(n\) 為 \(gcd(n_1, n_2)\) 的整數倍時，式 \((2)\) 必然會有整數解，即 \((p, q) = r(p', q')\)，其中 r 為整數。但是如果 \(n\) 不為 \(gcd(n_1, n_2)\) 的整數倍時，式 \((2)\) 會有整數解嗎？答案為否，這是因為 \(n\) 為 \(gcd(n_1, n_2)\) 的整數倍是式 \((2)\) 有整數解的必要條件（見證明：命題一），所以找到 \(gcd(n_1, n_2)\) 是當前的首要目標。
利用擴展歐幾里得演算法，可以在求得 \(gcd(n_1, n_2)\) 的同時，得到一組滿足式 \((3)\) 的解，稱其為 \((p_0', q_0')\)（這又被稱為 \((n_1, n_2)\) 的一組貝祖係數）。若 \(n\) 模除 \(gcd(n_1, n_2)\) 不為 \(0\)，表無論 \(n_1\) 和 \(n_2\) 怎樣組合都不會得到 \(n\)，也就是無解；若為 \(0\)，則可以透過將 \((p_0', q_0')\) 乘上 \(\frac{n}{gcd(n_1, n_2)}\) 得到一組滿足式 \((2)\) 的解，稱其為 \((p_0, q_0)\)。
考慮式 \((2)\)，知道其法向量為 \((n_1, n_2)\)，根據兩正交向量內積為 \(0\) 的性質，可以算出其方向向量可為 \((-n_2, n_1)\)，利用方向向量和 \((p_0, q_0)\) 得到其參數式為
\[ \begin{equation} \left\{ \begin{array}{} p = p_0 - n_2 t \\ q = q_0 + n_1 t \end{array} \right. \end{equation} \]
由於 \(p\) 和 \(q\) 為非負整數，故 \(t\) 的取值範圍並非為全體實數，但也不是整數，為什麼呢？先討論 \(p\)，因為 \(p_0\) 為整數，為使 \(p\) 為整數，則 \(n_2 t\) 也得為整數，考慮 \(n_2 t\) 可以形成的最小正整數為 \(n_2 \over gcd(n_1, n_2)\)，由於 \(n_2\) 是整數，所以 \(t\) 必須是以 \(gcd(n_1, n_2)\) 為分母，任意整數為分子的分數，為方便討論，把分母移給 \(n_2\)，令 \(t'\) 為 \(t\) 的分子，這樣對任意整數 \(t'\)，可以得到相應的整數 \(p\)，同理，\(q\) 也能以 \(t'\) 表示，改寫式 \((4)\) 得
\[ \begin{equation} \left\{ \begin{array}{} p = p_0 - \frac{n_2}{gcd(n_1, n_2)} t' \\ q = q_0 + \frac{n_1}{gcd(n_1, n_2)} t' \end{array} \right. \end{equation} \]
把式 \((5)\) 帶入 \(f(p, q)\)，得到
\[ \begin{eqnarray} f(p, q) &=& c_1 p + c_2 q \nonumber \\ &=& c_1(p_0 - \frac{n_2}{gcd(n_1, n_2)} t') + c_2(q_0 + \frac{n_1}{gcd(n_1, n_2)} t') \nonumber \\ &=& (c_1 p_0 + c_2 q_0) + (\frac{-c_1 n_2 + c_2 n_1}{gcd(n_1, n_2)}) t' \\ &=& g(t') \nonumber \end{eqnarray} \]
帶入後，原本關於 \(p\) 和 \(q\) 的函數轉變為關於 \(t'\) 的函數，同時不難發現 \(c_1 p_0 + c_2 q_0\) 和 \(\frac{-c_1 n_2 + c_2 n_1}{gcd(n_1, n_2)}\) 都為整數常數，也就是說 \(g(t')\) 是線性的，那麼只要知道 \(t'\) 的上下界並帶入 \(g(t')\)，就可知道 \(g(t')\) 是嚴格遞增或嚴格遞減函數，並得知最小值發生在何處。
現在來推 \(t'\) 的範圍，考慮 \(p\) 和 \(q\) 不能為負數，有 \(p \ge 0\) 和 \(q \ge 0\)，綜合式 \((5)\) 有
\[ \begin{equation} \left\{ \begin{array}{} p = p_0 - \frac{n_2}{gcd(n_1, n_2)} t' \ge 0 \\ q = q_0 + \frac{n_1}{gcd(n_1, n_2)} t' \ge 0 \end{array} \right. \end{equation} \]
整理式 \((7)\)，得到
\[ \begin{equation} \left\{ \begin{array}{} t' \le \left \lceil{\frac{p_0 \times gcd(n_1, n_2)}{n_2}}\right \rceil \\ t' \ge \left \lfloor{\frac{-q_0 \times gcd(n_1, n_2)}{n_1}}\right \rfloor \end{array} \right. \end{equation} \]
所以 \(t'\) 的範圍為 \(\left \lceil{\frac{p_0 \times gcd(n_1, n_2)}{n_2}}\right \rceil \le t' \le \left \lfloor{\frac{-q_0 \times gcd(n_1, n_2)}{n_1}}\right \rfloor\)，若該範圍中不存在任何整數，表無解，否則按前述方法求得 \(t'_{min}\)，再把 \(t'_{min}\) 帶入式 \((5)\) 回推得出 \(p_{min}\) 和 \(q_{min}\)，即為式 \((1)\) 的答案。
範例
1 | 1024 |
A. 求 \(gcd(34, 20)\)，得到 \(gcd(34, 20) = 2\)。
\[ \begin{array}{} 34 &\div& 20 &=& 1 &\dots& 14 \\ 20 &\div& 14 &=& 1 &\dots& 6 \\ 14 &\div& 6 &=& 2 &\dots& 2 \\ 6 &\div& 2 &=& 3 &\dots& 0 \\ \end{array} \]
B. 藉由回推求 \(gcd(34, 20)\) 的過程得到 \((34, 20)\) 的一組貝祖係數 \((3, -5)\)。
\[ \begin{eqnarray*} gcd(34, 20) &=& 2 \\ &=& 14 - 2 \times 6\\ &=& 14 - 2 \times (20 - 14) \\ &=& 3 \times 14 - 2 \times 20 \\ &=& 3 \times (34 - 20) - 2 \times 20 \\ &=& 3 \times 34 - 5 \times 20 \\ &=& 3 \times 34 + (-5) \times 20 \end{eqnarray*} \]
C. \(1024\) 模除 \(2\) 為 \(0\)，繼續。
D. 求 \((p_0, q_0)\)，得 \((p_0, q_0) = \frac{1024}{2} \times (3, -5) = (1536, -2560)\)。
E. 求 \(\left \lceil{\frac{-(-2560 \times 2)}{34}}\right \rceil \le t' \le \left \lfloor{\frac{1536 \times 2}{20}}\right \rfloor\)，得 \(151 \le t' \le 153\)，繼續。
F. 由於 \(g(151) = 729 < g(153) = 759\)，取 \(t'_{min} = 151\)。
G. 將 \(t'_{min}\) 帶入式 \((5)\)，得到答案為 \((26, 7)\)。
\[ \begin{eqnarray*} (p_{min}, q_{min}) &=& (1536 - \frac{20}{2} \times 151, -2560 + \frac{34}{2} \times 151) \\ &=& (26, 7) \end{eqnarray*} \]
結論
本題結合了數論與函數的應用，可謂是相當精彩，除非有超強的數學直覺，否則在不知道貝祖定理、擴展歐幾里得演算法或數學推理能力不足的情況下（完全在說我自己），要解出本題是有些難度的。
備註
- 文中關於貝祖等式的說明翻譯自 Bézout's identity。
- 顯然當 \(n < n_1\) 且 \(n < n_2\) 時式 \((2)\) 無法被滿足，可以事先檢查避免多餘的運算，不過不檢查也不會出錯，因為這會在步驟 E. 得到無解。
- \(g(t')\) 不會是水平線，因為題目表明當式 \((1)\) 有解時，可以假設其解唯一。
- 範例的 A. 和 B. 在擴展歐幾里得演算法中是同時進行的。
證明
命題一：若 \(n_1 p + n_2 q = n\) 存在整數解，則 \(n\) 為 \(gcd(n_1, n_2)\) 的整數倍。
令 \(d\) 表 \(gcd(n_1, n_2)\)，因為 \(n_1\) 和 \(n_2\) 為 \(d\) 的整數倍，不仿設 \(n_1 = r_1 d\) 和 \(n_2 = r_2 d\)，其中 \(r_1, r_2 \in \mathbb{Z}\)。由於存在整數解使得 \(n_1 p + n_2 q = n\) 成立，故 \((r_1 d) p + (r_2 d) q = n\) 也成立，整理得 \(n = (r_1 p + r_2 q)d\)，顯然 \((r_1 p + r_2 q)\) 為一整數，證畢。