问题描述

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 * (x₀a + y₀b) = (1-qx₀)a + (-qy₀)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，构造数列{u_n}, u₀ = a，u₁ = b，u_k = u_k-2 mod u_k-1，若总共需要n次模运算，则u_n = gcd(a, b)，u_n+1 = 0。
我们比较数列{u_n}和斐波那契数列{Fn}， F₀ = 1<=u_n , F₁ =1<=u_n-1，因为u_k+2 >= u_k+1 + u_k，因此u_k >= F_n-k，因此，a = u₀ >= F_n，b = u₁ >= F_n-1，这就是说，如果辗转相除法要做n次模运算，则b >= F_n-1， 若b < F_n-1，则模运算次数必小于n。
根据斐波那契数列的性质：F_n-1 > (1.618)ⁿ / 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