365. 水壶问题

【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
那么操作主要是：

1. 灌满x， 结束；=> +x
2. 灌满y， 结束；=> +y
3. 灌满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