應用：倒水問題

想法：轉化成丟番圖問題

根據貝祖定理，由於 \(\gcd(A, B)=1\)，因此存在兩個整數 \(x\) 與 \(y\) 使得 \(xA+yB=C\)。 若我們得知了 \(x\) 與 \(y\) 之值滿足 \(xA+yB = C\)，那麼便存在一個倒水方案：欲湊出 \(C\) 毫升的水，我們可以讓容量為 \(A\) 毫升的杯子斟滿 (或清空) \(|x\vert \) 次、讓容量為 \(B\) 毫升的杯子斟滿 (或清空) \(|y\vert \) 次。因此經過一番推敲後，不難得知需要的總次數不超過 \(|x\vert +\vert y\vert \)。此外，任何湊出 \(C\) 毫升滿足題目設定的倒水方案，總是會對應著一組整數 \(x', y'\) 使得 \(x'A+y'B=C\)。於是原本問題便轉化成了丟番圖問題：找出滿足 \(xA+yB=C\) 的所有整數解 \((x, y)\) 中，最小的 \(|x\vert +\vert y\vert \) 之值。

從線性丟番圖的解法來看，我們可以先利用擴展歐幾里德演算法找出任何一組滿足 \(x'A+y'B=C\) 的一個解 \((x', y')\)，然後得知所有的解必定形如 \((x'+kB, y'-kA)\)，其中 \(k\in \mathbb{Z}\) 可以是任意整數。考慮實數函數 \(f(t)=\vert x'+tB\vert +\vert y'-tA\vert \)，不難發現他是兩個 V 形狀的函數的和，因此 \(f(t)\) 也是分段線性的凸函數。所以要找出最小值，要嘛可以直接暴力算出最低點兩邊的整數值，或是用二分搜尋法找最低點也行。