倒水問題數學解法：以最大公因數判斷目標水量可行性

經典「倒水問題」給定兩個容量分別為 A、B 公升的容器與無限水源，僅允許「灌滿、倒空、互倒」三種操作，問能否在一足夠大的水缸中精確得到 C 公升水。本文證明此問題的可行性完全取決於 gcd(A, B) 是否整除 C，並提供 O(log min(A,B)) 的高效判斷演算法。

問題數學模型

每次操作本質上是在兩容器之間轉移水量，系統狀態可用有序對 (x, y) 表示（分別為兩容器當前水量）。所有可達狀態的水量皆為 A、B 的整數線性組合：

x = m·A + n·B (m, n ∈ ℤ)

根據數論貝祖等式，這類線性組合能表示的整數集合正是 gcd(A, B) 的倍數集合。由於水缸只能倒入、不能倒出，最終水缸水量等於所有「倒入水缸」操作的水量總和，同樣屬於上述集合。

充要條件定理

定理：存在有限步驟使水缸恰好有 C 公升水 ⇔ C % gcd(A, B) == 0。

• 必要性：每次倒入水缸的水量皆為 A、B 的線性組合，故總和必為 gcd(A, B) 的倍數。
• 充分性：若條件成立，擴展歐幾里得演算法可構造出具體操作序列（略）。

高效判斷演算法（C/C++ 實作）

// 遞迴版 GCD
int gcd(int a, int b) {
    if (a < b) return gcd(b, a);
    if (b == 0) return a;
    return gcd(b, a % b);
}

bool canMeasure(int a, int b, int c) {
    return c % gcd(a, b) == 0;
}

或使用尾遞迴/迭代寫法避免堆疊溢位：

int gcd_iter(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

複雜度分析

• 時間：O(log min(A, B))，歐幾里得演算法對數級收斂。
• 空間：遞迴版 O(log min(A, B)) 堆疊深度；迭代版 O(1)。

邊界情況處理

• C > A + B：題目設定水缸「足夠大」，故不限制上限；若水缸有容量上限需額外檢查。
• A == 0 || B == 0：題目限制 0 < A, B, C，無需處理零容器。
• 大數值（≤ 10⁹）：32 位有號整數足夠，無溢位風險。

總結

倒水問題看似需 BFS/DFS 搜尋狀態空間，實則為數論經典應用。掌握 gcd 判斷法，可在 O(log N) 時間內給出 Yes/No 答案，並為構造具體操作序列奠定理論基礎。