### 题目

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


### 贝祖等式

x = 4, y = 6, z = 8.


1. 倒满6升的y壶
2. 6升的y壶向4升的x壶里倒水，直到倒满x壶。此时y壶还剩2升水
3. 把x壶里的4升水倒掉
4. 把y壶里剩余的2升倒进x壶
5. 再重新倒满6升的y壶

6 - 4 + 6


-1 * 4 + 2 * 6 = 8


4x + 6y = c

6和4的最大公约数为2，也就是只有当c是2的整数倍的时候，x和y才有整数解。例子里c = 8，确实是2的整数倍，所以有解。

### 最大公倍数（GCD: Greatest Common Divisor）

1. a % b = d
2. 如果d == 0，则最大公约数就是b
3. 否则，令a = bb = d，重复以上步骤

gcd(a,b)=gcd(b,a mod b)

#### 代码

class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (x < 0 || y < 0 || z < 0 || z > x + y) {
return false;
}
// assert: x,y,c are all valid input
if (z == 0) {
return true;
}
// special cases: x == 0 || y == 0 && z > 0
if (x == 0 || y == 0) {
return x + y == z;
}
// assert: a > 0 && b > 0 && z > 0
return (z % gcd(x, y)) == 0;
}
// 计算a和b的最大公约数
// assert: a > 0 && b > 0
private int gcd(int a, int b) {
int mod = a % b;
if (mod == 0) { return b; }
return gcd(b, mod);
}
}