问题描述
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 = 4Output: True
Example 2:
Input: x = 2, y = 6, z = 5Output: False
问题分析
这是一个很常见的问题，但之前我没有把它当成编程题做过，而只做过实例。
做法很简单，若z是x和y最大公约数的整数倍，则其可以被两个杯子称量。
问题是为什么是这么做的。
证明
裴蜀定理：对任意整数a、b和它们的最大公约数d，关于未知数x，y的线性丢番图方程（称为裴蜀等式）
ax + by = m
有整数解当且仅当m是d的倍数。
设d = gcd(a, b)， 则d|a且d|b，对任意整数x、y，有d|(xa + yb)；
设s为xa + yb的最小正值，显然d|s；
设q = ⌊a/s⌋， r = a % s，则r = a - q*s = a - q * (x0a + y0b) = (1-qx0)a + (-qy0)b，可见r也是a、b的线性组合；
而0<=r<s，因此r=0，即s|a，同样s|b，因此s|d；
因此s = d，即由a、b线性组成的值最小为d，由a、b线性组成的值可为d的任意整数倍。
最大公约数和最小公倍数
辗转相除法求最大公约数gcd：
例如，求（319，377）：
∵ 319÷377=0（余319）
∴（319，377）=（377，319）；
∵ 377÷319=1（余58）
∴（377，319）=（319，58）；
∵ 319÷58=5（余29），
∴ （319，58）=（58，29）；
∵ 58÷29=2（余0），
∴ （58，29）= 29；
∴ （319，377）=29。
辗转相除法的时间复杂度：
参考关于欧几里得算法的时间复杂度。
我们来看辗转相除法最多要做多少次模运算。设a>b>=1，构造数列{un}, u0 = a，u1 = b，uk = uk-2 mod uk-1，若总共需要n次模运算，则un = gcd(a, b)，un+1 = 0。
我们比较数列{un}和斐波那契数列{Fn}， F0 = 1<=un , F1 =1<=un-1，因为uk+2 >= uk+1 + uk，因此uk >= Fn-k，因此，a = u0 >= Fn，b = u1 >= Fn-1，这就是说，如果辗转相除法要做n次模运算，则b >= Fn-1， 若b < Fn-1，则模运算次数必小于n。
根据斐波那契数列的性质：Fn-1 > (1.618)n / sqrt(5)， 因此模运算次数为O(logn)。
最小公倍数：
a、b的最小公倍数=a * b / gcd(a, b)。
AC代码
class Solution(object):
def canMeasureWater(self, x, y, z):
"""
:type x: int
:type y: int
:type z: int
:rtype: bool
"""
if z == 0:
return True
if z > x + y:
return False
if x == 0:
if y == 0:
return False
else:
return z % y == 0
elif y == 0:
return z % x == 0
gcd = self.getGCD(x, y)
if z % gcd == 0:
return True
return False
def getGCD(self, x, y):
while x % y != 0:
x, y = y, x % y
return y
