LeetCode 365. 水壶问题

有两个容量分别为 x 升和 y 升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z 升的水？
如果可以，最后必须用以上水壶中的一或两个来盛放取得的 z 升水。
允许做以下操作：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1:（出自电影《虎胆龙威》）

1 2	输入: x = 3, y = 5, z = 4 输出: True

操作方法：先把A壶加满，倒入B壶，再把A壶加满，倒入B壶，此时A、B各有1升和5升水。倒光B壶，把A壶中的1升水倒入B壶，加满A壶，倒入B壶，此时B壶即有4升水。

示例 2:

1 2	输入: x = 2, y = 6, z = 5 输出: False

题解:
如果从纯算法角度来考虑该问题，那么 DFS 或者 BFS 都可以。以 (A壶水量, B壶水量) 作为状态去搜索。每个状态需要搜下面这 6 种情况：

装满A壶
装满B壶
清空A壶
清空B壶
从A壶向B壶倒水，直到装满或者倒空
从B壶向A壶倒水，直到装满或者倒空

为了防止无限递归，需要建立一个 HashSet 来存储已经搜索过的状态，保证每个状态最多只被搜到一次。由于搜索深度很深，递归实现容易爆栈，所以可以用栈（队列）实现 DFS（BFS）。
无论 DFS 还是 BFS，因为最多有 $(x+1)(y+1)$ 种状态，所以时间复杂度和空间复杂度都是 $O(xy)$。反正我写的 DFS 在 LeetCode 上 TLE 了😩

然而此题有个绝妙的数学解法，可秒杀 DFS/BFS：
我们首先需要明确，在初始状态下，两个水壶中水的总量是 0，之后，不管我们做六种操作的哪一种，都只会使水的总量 增加x 或 增加y 或 减少x 或 减少y。注意，两个水壶不会同时半满，所以如果我们把半满的水壶倒空或接满，虽然水的总量的变化量不是 x 或 y，但是这么操作之后就又回到了 一个空一个满 或 两个空 或 两个满 的状态，所以把半满的水壶倒空或接满这类操作是无意义的。
所以，水的总量的变化量一定是 x 或 y，由此我们可以得知水的总量永远等于 $ax+by$，其中$a,b\in Z$。这样一来，获取 z 升水的充要条件就是 $z\leq x+y$ 并且方程 $ax+by=z$ 有整数解。
由贝祖定理（或称裴蜀定理）可知，$ax+by=z$ 有解当且仅当 $z$ 是 $x, y$ 的最大公约数的倍数。所以此题数学解法的代码如下：

代码:

int gcd(int a, int b)   // 求最大公约数
{
    return b ? gcd(b, a%b) : a;
}

bool canMeasureWater(int x, int y, int z)
{
    if(z > x + y)
        return false;
    else if(x == 0 && y == 0 && z == 0)
        return true;
    else
        return z % gcd(x, y) == 0;
}

这种解法的时间复杂度等于辗转相除法求最大公约数的时间复杂度，即 $O(\log(\min \lbrace x, y\rbrace ))$，空间复杂度为 $O(1)$。