class Solution:
    """
    @param x: the given number x
    @param y: the given number y
    @param z: the given number z
    @return: whether it is possible to measure exactly z litres using these two jugs
    """
    def canMeasureWater(self, x, y, z):
        # Write your code here
        '''
        easily get z is legal => z = M * x + N * y and 0 <= z <= x + y

        prove converse proposition:
        if z >= x, we could pour x-jug full and empty it, z' = z - x, M -= 1, z' is legal
        if z <= x, we could pour all water to x-jug and fill y-jug, z' = z + y, N += 1, z' is legal
        similar with z >= y, N -= 1, z <= y, M += 1

        for given z = M * x + N * y and 0 <= z <= x + y, it must be
        1. M == 1 and N == 1, easily comes z is legal
        2. M > 0 and N < 0, by transform of M -= 1 and N += 1, one of M or N will
           firstly reach 0. it can't be M since now z = N * y < 0 not legal. so N
           will firstly reach 0 and z = M * x, and M -= 1 * M now z is 0, a legal
           initiation status.
        3. M < 0 and N > 0. similar
        '''
        return z % math.gcd(x, y) == 0 and 0 <= z <= x + y