Math-365-Water and Jug Problem

Description:
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

Best Solution:

public boolean canMeasureWater(int x, int y, int z) {
    //limit brought by the statement that water is finallly in one or both buckets
    if(x + y < z) return false;
    //case x or y is zero
    if( x == z || y == z || x + y == z ) return true;

    //get GCD, then we can use the property of B\xe9zout's identity
    return z%GCD(x, y) == 0;
}

public int GCD(int a, int b){
    while(b != 0 ){
        int temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}

这题涉及到数论Bézout’s identity，链接如下:https://en.wikipedia.org/wiki/B%C3%83%C2%A9zout‘s_identity
大意是，若a和b有最大公约数d，那么存在ax+by=d(d是这种表示法得到的最小的数，还可以得到d的整数倍),而假如有z%d=0，那么z也可以表示为ax+by的形式
回到问题。我们将x,y定义如下:
a or b>0,表示我们将x或y装满
a or b <0,表示我们将x或y倒空

比如x = 4,y = 6,z = 8,那么可以得到4 * (-1) + y * 2 = 8,即为,将x放空一次，y倒满两次。实际操作流程如下,y装满,将y中的4升倒入x(由于不是将水壶中的水直接倒入x，因此x的系数不变),将x中的4升倒出（此时a为-1）,将y中的两升倒入x,将y倒满,因此a=-1，b=2