【Description】
有两个容量分别为 x升 和* y*升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 *z升 *水。
你允许：
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例1：
输入: x = 3, y = 5, z = 4
输出: True
示例2：
输入: x = 3, y = 5, z = 4
输出: True
【Idea】
先考虑特殊情况：
z==0（直接输出true） / x+y <z （直接凑不了）/ x, y有一方=0， 只能靠另一方凑
然后进入正题。
目标函数： ax+by=z
假设x<=y，那么a可以取负值，对应操作：x壶灌满水后倒入y壶里 | 0<=b<=1
那么操作主要是：
- 灌满x， 结束；=> +x
- 灌满y， 结束；=> +y
- 灌满x后倒入y（y未满）=> +(y-x)
结合以上三种增量，把y-x 变换成: -x+y就是ax+by(a=-1, b=1)的一个示例。
因此可以套入贝祖定理（若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立）
所以最后就是求x，y的最小公约数，用z整除求解即可。
（其实最开始写的时候也不知道这个定理，就是感觉x, y,和y-x求个最小公约数就OK了。 看题解才知道这还是个定理，还挺没文化的hh
【Solution】
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if z == 0:
return True
if x+y < z:
return False
if min(x, y)==0 and max(x, y) != z:
return False
gongyue = 1
for i in range(1, min(x, y)+1):
if x%i == 0 and y%i == 0:
gongyue = i
if z % gongyue == 0:
return True
else:
return False
