题目描述

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.

Operations allowed:

• Fill any of the jugs completely.
• 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.

解题思路

这个问题实质上是求解关于a和b的方程ax+by=z是否有整数解的问题。a和b为正数时表示给一个空壶倒满水，负数时表示把一个水壶倒空。容易得知当且仅当z是x与y的最小公约数的倍数时，该方程有整数解，所以本题的关键是判断z被x和y的最大公约数整除即可，关键的算法是辗转相除法。

目前尚存在争议的一个问题是在最后量取的步骤中水壶能否被多次使用（比如x=1, y=2, z=5的情况，是否可以用1+2+2=5来实现），该问题的讨论区里也在讨论中。目前的test cases好像是认定为最终只能用两个水壶在某一时刻里存有的总水量来衡量，所以z>x+y的情况都判定为false了。

代码

class Solution {
public:
    int gcd(int x, int y)  
    {
        return y==0?x:gcd(y, x%y);  
    }
    bool canMeasureWater(int x, int y, int z) {
        if(z < 0 || z > x + y)
            return false;
        if(z % gcd(x, y))
            return false;
        else
            return true;
    }
};