LeetCode Water and Jug Problem You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs. If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end. Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous “Die Hard” example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

---

很有意思的水罐问题。给定一个3L的水罐和一个5L的水罐和无限的水，问怎样才能得到4L的水。 这个例子很常见了，可以这样做：

1. 盛满5L水罐；
2. 将5L水罐中的水导入3L水罐，此时5L水罐中还剩2L水；
3. 将3L水罐中的水清空；
4. 将5L水罐中的2L水倒入3L水罐中；
5. 盛满5L水罐；
6. 将5L水罐中的水倒入3L水罐中，此时5L水罐中剩余4L水，3L水罐中是满的；
7. 将3L水罐中的水清空，此时只剩5L水罐中的4L水。

但是遇到一般的x、y、z时，怎样解呢，这里面肯定暗含某种数学规律，看了题解才恍然大悟。 将问题转换为这样一个问题：给定xL和yL水罐和无限的水，以及一起无穷大的水罐，怎样利用x和y才能在无穷大的水罐中盛满zL的水。假设我们要往无穷大的水罐中倒m次xL的水和n次yL的水，则有mx+ny=z，如果m为正，则是倒入，为负则是舀出。比如x=3, y=5, z=4时，有(-2)*3+2*5=4，表示往无穷大的水罐中倒入2次5L的水，并且舀出2次3L的水，剩余正好4L。而上面的7步正好也包含2次盛满5L水，2次清空3L水。 所以问题就转换为方程mx+ny=z对于m,n是否有整数解。这需要用到裴蜀定理，又是头一回听说。 假设x和y的最大公约数是d=gcd(x,y)，如果z是d的整数倍，则上式有整数解。所以问题就好办了，求一下x,y的最大公约数，然后判断z是否是最大公约数的整数倍就好了。 另外要保证x+y>=z，因为如果x和y加起来的容量都没有z大，怎么可能使得两个罐中水量之和正好等于z呢。 代码如下： [cpp] class Solution { private: int gcd(int x, int y) { return y == 0 ? x : gcd(y, x%y); } public: bool canMeasureWater(int x, int y, int z) { return z == 0 || (x + y >= z&&z%gcd(x, y) == 0); } }; [/cpp] 本代码提交AC，用时0MS。]]>