可以想象有一个无限大的水罐,如果我们有两个杯子x和y,那么原来的问题等价于是否可以通过往里面注入或倒出水从而剩下z。
z =? m*x + n*y
如果等式成立,那么z%gcd(x,y) == 0。
class Solution(object):
def canMeasureWater(self, x, y, z):
"""
:type x: int
:type y: int
:type z: int
:rtype: bool
"""
if z == 0 or (z<= x+y and z%self.gcd(x,y) == 0):
return True
else:
return False def gcd(self, x, y):
while y != 0:
(x, y) = (y, x % y)
return x