Water and Jug Problem 水壶问题

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

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

示例 1: (From the famous "Die Hard" example)

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

示例 2:

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

思路：这道题可以转化成经过多少次倒水和出水，最后满足等式：ax+by=z，其中x和y是两个桶的容量，z是最后能得到的z升水，a和b是待求的未知数且正数表示往杯子里倒水，出水表示往杯子外倒水，根据数学方法，z的解满足如下等式：z=gcd(x,y)，gcd表示最大公约数，那么这道题就可以就可以转化成求出未知数z_tmp，如果z_tmp是待求的z的最大公约数，那么返回true，同时要注意约束条件：x+y>=z

参考代码：

class Solution {
public:
    int gcd2(int m, int n) {
        if (n == 0) return m;
        return gcd2(n, m%n);
    }
    bool canMeasureWater(int x, int y, int z) {
        //边界条件判断
        if(x==0) return y==0?z==0:(z%y)==0;
        if(y==0) return x==0?z==0:(z%x)==0;
        //解方程ax+by=z，那么z=gcd(x,y)
        int c_tmp = gcd2(x, y);
        return (z % c_tmp == 0) && (x + y) >= z;
    }
};