题目描述
有两个容量分别为 x升 和y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。
你允许：
- 装满任意一个水壶
- 清空任意一个水壶
- 从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例
示例 1：
输入: x = 3, y = 5, z = 4
输出: True
示例2：
输入: x = 2, y = 6, z = 5
输出: False
解答方法
方法一：数学法
思路
如果gcd(x,y) = k ，那么肯定有整数（正的或负的）m与n，使得 mx + ny = k
如果z % k == 0, 那么mx + ny = k那么必定存在一个常数g使得g(mx + ny) == k * g == z
所以题目就转换为寻找x，y的最大公约数。
代码
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if x+y<z:
return False
if z == 0 or x+y ==z:
return True
return z%math.gcd(x,y) == 0
# def gcd(a,b):
# if b==0:
# return a
# else:
# return gcd(b, a%b)
时间复杂度
O(log(min(x,y)))，取决于计算最大公约数所使用的辗转相除法。
空间复杂度
O(1)O(1)，只需要常数个变量。
