UVa 10090: Marbles

描述

給定 $n$ 顆彈珠和兩種盒子，且兩種盒子的花費和容量分別為 $c_1$、$c_2$ 和 $n_1$、$n_2$，其中 $n$、$c_1$、$c_2$、$n_1$ 和 $n_2$ 都是正整數，現在用數量不定的兩種盒子裝彈珠，並且所有盒子都必須裝滿，若能辦到，問在最低花費下，兩種盒子的所需個數為多少。

思路

令 $p$ 和 $q$ 分別為兩種盒子所需的數量，則題目可以表述為

$$\begin{array}{}\text{(1)}& \underset{p,q}{\mathrm{argmin}}f(p,q)=c_{1}p+c_{2}q\end{array}$$

且 $p,q\in {\mathbb{Z}}^{0+}$ 並同時滿足

$$\begin{array}{}\text{(2)}& n_{1}p+n_{2}q=n\end{array}$$

第一層

既然 $n$ 的上限是 $20,0000,0000$，就不浪費篇幅討論暴力解了，直接進入主題。

第二層

式 $(2)$ 顯然為二元一次丟番圖方程式，並且容易想到（？）貝祖等式，貝祖等式的內容為

令 $a$ 和 $b$ 為整數且兩者的最大公因數為 $d$，則存在整數 $x$ 和 $y$ 使得 $ax+by=d$。

據此有

$$\begin{array}{}\text{(3)}& n_1{p}^{\prime }+n_2{q}^{\prime }=gcd(n_1,n_2)\end{array}$$

觀察式 $(2)$ 和式 $(3)$，兩者的不同在於等號右邊分別為 $n$ 和 $gcd(n_1,n_2)$，當 $n$ 為 $gcd(n_1,n_2)$ 的整數倍時，式 $(2)$ 必然會有整數解，即 $(p,q)=r(p^{\prime },q^{\prime })$，其中 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^{\prime },q_0^{\prime })$（這又被稱為 $(n_1,n_2)$ 的一組貝祖係數）。若 $n$ 模除 $gcd(n_1,n_2)$ 不為 $0$，表無論 $n_1$ 和 $n_2$ 怎樣組合都不會得到 $n$，也就是無解；若為 $0$，則可以透過將 $(p_0^{\prime },q_0^{\prime })$ 乘上 $\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{array}{}\text{(4)}& \{\begin{array}{}p=p_0-n_{2}t\\ q=q_0+n_{1}t\end{array}\end{array}$$

由於 $p$ 和 $q$ 為非負整數，故 $t$ 的取值範圍並非為全體實數，但也不是整數，為什麼呢？先討論 $p$，因為 $p_0$ 為整數，為使 $p$ 為整數，則 $n_{2}t$ 也得為整數，考慮 $n_{2}t$ 可以形成的最小正整數為 $\frac{n_2}{gcd(n_1,n_2)}$，由於 $n_2$ 是整數，所以 $t$ 必須是以 $gcd(n_1,n_2)$ 為分母，任意整數為分子的分數，為方便討論，把分母移給 $n_2$，令 $t^{\prime }$ 為 $t$ 的分子，這樣對任意整數 $t^{\prime }$，可以得到相應的整數 $p$，同理，$q$ 也能以 $t^{\prime }$ 表示，改寫式 $(4)$ 得

$$\begin{array}{}\text{(5)}& \{\begin{array}{}p=p_0-\frac{n_2}{gcd(n_1,n_2)}{t}^{\prime }\\ q=q_0+\frac{n_1}{gcd(n_1,n_2)}{t}^{\prime }\end{array}\end{array}$$

把式 $(5)$ 帶入 $f(p,q)$，得到

$$\begin{array}{rcl}f(p,q)& =& c_{1}p+c_{2}q\\ & =& c_1(p_0-\frac{n_2}{gcd(n_1,n_2)}{t}^{\prime })+c_2(q_0+\frac{n_1}{gcd(n_1,n_2)}{t}^{\prime })\\ \text{(6)}& & =& (c_1{p}_0+c_2{q}_0)+(\frac{-c_1{n}_2+c_2{n}_1}{gcd(n_1,n_2)})t^{\prime }& =& g(t^{\prime })\end{array}$$

帶入後，原本關於 $p$ 和 $q$ 的函數轉變為關於 $t^{\prime }$ 的函數，同時不難發現 $c_1{p}_0+c_2{q}_0$ 和 $\frac{-c_1{n}_2+c_2{n}_1}{gcd(n_1,n_2)}$ 都為整數常數，也就是說 $g(t^{\prime })$ 是線性的，那麼只要知道 $t^{\prime }$ 的上下界並帶入 $g(t^{\prime })$，就可知道 $g(t^{\prime })$ 是嚴格遞增或嚴格遞減函數，並得知最小值發生在何處。

現在來推 $t^{\prime }$ 的範圍，考慮 $p$ 和 $q$ 不能為負數，有 $p\ge 0$ 和 $q\ge 0$，綜合式 $(5)$ 有

$$\begin{array}{}\text{(7)}& \{\begin{array}{}p=p_0-\frac{n_2}{gcd(n_1,n_2)}{t}^{\prime }\ge 0\\ q=q_0+\frac{n_1}{gcd(n_1,n_2)}{t}^{\prime }\ge 0\end{array}\end{array}$$

整理式 $(7)$，得到

$$\begin{array}{}\text{(8)}& \{\begin{array}{}{t}^{\prime }\le \lceil \frac{p_0\times gcd(n_1,n_2)}{n_2}\rceil \\ t^{\prime }\ge \lfloor \frac{-q_0\times gcd(n_1,n_2)}{n_1}\rfloor \end{array}\end{array}$$

所以 $t^{\prime }$ 的範圍為 $\lceil \frac{p_0\times gcd(n_1,n_2)}{n_2}\rceil \le t^{\prime }\le \lfloor \frac{-q_0\times gcd(n_1,n_2)}{n_1}\rfloor$，若該範圍中不存在任何整數，表無解，否則按前述方法求得 $t_{min}^{\prime }$，再把 $t_{min}^{\prime }$ 帶入式 $(5)$ 回推得出 $p_{min}$ 和 $q_{min}$，即為式 $(1)$ 的答案。

範例

1024
24 34
15 20

A. 求 $gcd(34,20)$，得到 $gcd(34,20)=2$。

$$\begin{array}{}34& ÷& 20& =& 1& \dots & 14\\ 20& ÷& 14& =& 1& \dots & 6\\ 14& ÷& 6& =& 2& \dots & 2\\ 6& ÷& 2& =& 3& \dots & 0\end{array}$$

B. 藉由回推求 $gcd(34,20)$ 的過程得到 $(34,20)$ 的一組貝祖係數 $(3,-5)$。

$$\begin{array}{rcl}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{array}$$

C. $1024$ 模除 $2$ 為 $0$，繼續。

D. 求 $(p_0,q_0)$，得 $(p_0,q_0)=\frac{1024}{2}\times (3,-5)=(1536,-2560)$。

E. 求 $\lceil \frac{-(-2560\times 2)}{34}\rceil \le t^{\prime }\le \lfloor \frac{1536\times 2}{20}\rfloor$，得 $151\le t^{\prime }\le 153$，繼續。

F. 由於 $g(151)=729<g(153)=759$，取 $t_{min}^{\prime }=151$。

G. 將 $t_{min}^{\prime }$ 帶入式 $(5)$，得到答案為 $(26,7)$。

$$\begin{array}{rcl}(p_{min},q_{min})& =& (1536-\frac{20}{2}\times 151,-2560+\frac{34}{2}\times 151)\\ & =& (26,7)\end{array}$$

結論

本題結合了數論與函數的應用，可謂是相當精彩，除非有超強的數學直覺，否則在不知道貝祖定理、擴展歐幾里得演算法或數學推理能力不足的情況下（完全在說我自己），要解出本題是有些難度的。

備註

• 文中關於貝祖等式的說明翻譯自 Bézout's identity。
• 顯然當 $n<n_1$ 且 $n<n_2$ 時式 $(2)$ 無法被滿足，可以事先檢查避免多餘的運算，不過不檢查也不會出錯，因為這會在步驟 E. 得到無解。
• $g(t^{\prime })$ 不會是水平線，因為題目表明當式 $(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)$ 為一整數，證畢。