问题描述

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.

问题分析

这是一个很常见的问题，但之前我没有把它当成编程题做过，而只做过实例。
做法很简单，若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的最小公倍数=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