365. Water and Jug Problem

This is a pure math problem. This problem requires us to get x and y such that xa+xy=z. To solve this problem, we need to know two maths:

(1). Bezout's lemma tells us that: let a and be be nonzero integers and let d be their greatest common divisor. Then there exist integers x and y such that ax+by=d.
From the lemma, the problem becomes if z can be divided by gcd(a, b).

(2) to calculate gcd, we use Euclid's algorithm: gcd(a, b) = gcd(b, a%b).

1:  class Solution {  
2:  public:  
3:    bool canMeasureWater(int x, int y, int z) {  
4:      return z == 0 || z <= x + y && z % gcd(x, y) == 0;  
5:    }  
6:    int gcd(int a, int b) {  
7:      while (b) {  
8:        int temp = b;  
9:        b = a % b;  
10:        a = temp;  
11:      }  
12:      return a;  
13:    }  
14:  };