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.
Here I choose a math solution based on linear congruential formula:
 ax ≡ b (mod n)
Just take a try! (Example 1)
We can write down all the possible x and y (start from x = 0, y = 0, end at x = 3, y = 5 ):
 (0,0)
 (0,5)
 (3,2)
 (0,2)
 (2,0)
 (2,5)
 (3,4)
 (0,4)
 (3,1)
 (0,1)
 (1,0)
 (1,5)
 (3,3)
 (0,3)
 (3,0)
 (3,3)
 (3,5)
If we put these points to a 2D oblique coordinate system (θ = 60°), and draw the paths from the start to the end. We can get
If you imagine that
 The border lines (x = 0, y = 0, x = 3, y = 5) are mirrors
 The start point (0,0) is a light source
As the angle of incidence equals the angle of reflection, have you find that the route is light path diagram?
In the diagram, EACH REFLECTION POINT is A SOLUTION FOR (x,y)
Since what we need is the sum of x and y, note that:
 RED route: x is same.
 BLUE route: The value x + y of the start point is as same as the end point.
 (2,5) to (3,4)
 (1,5) to (3,3)
 (0,5) to (3,2)
 (0,4) to (3,1)
 (0,3) to (3,0)
 (0,2) to (2,0)
 (0,1) to (1,0)  GREEN route: y is same.
At first, I write a program to follow the light path diagram, but when x and y is too high, the program is slow.
Let's make it more general!
For normal y = p, x = q (p > q > 0), if we draw the paths (between 2 RED routes) in a 2D oblique coordinate system, we get
As the sum x + y keep the same on the BLUE route, we ONLY focus on the points on the yaxis.

From A0, we get (0, p  q), (0, p  2q), ... The last point is (0, r0), and r0 ≡ p (mod q).

x + y = p  q, p  2q, ..., r0. We can write p = kq + r0.
Result 1: If function returns TRUE, z is in {p  q, p  2q, ..., r0}.
 z ≡ r0 (mod q)
Then the RED route goes to B1, then BLUE route to C1.
If we extend B1C1 to the back, we get A1 on the yaxis, and the x + y in A1/B1/C1 is SAME.

From A1, we get (0, p  q + r0), (0, p  2q + r0), ... The last point is (0, r1)

x + y = p  q + r0, p  2q + r0, ..., r1

Here, r1 ≡ (p + r0) (mod q) ≡ (p mod q) + (r0 mod q) ≡ 2r0 (mod q)
Result 2: If function returns TRUE, z is in {p  q + r0, p  2q + r0, ..., r1}.
 z ≡ r1 (mod q) ≡ (2r0 mod q)
..........
Result k: If function returns TRUE.
 z ≡ r(k1) (mod q) ≡ kr0 (mod q)
Conclution
If function returns TRUE. There MUST EXIST a k, that kr0 ≡ z (mod q).
The problem becomes that whether the formula kr0 ≡ z (mod q) has a root k.
 If r0 = 0, then z mod q MUST equals to 0.
 If r0 ≠ 0, then:
 On wikipedia (线性同余方程), I get that I only need to judge whether gcd(r0,q)  z.
 About the gcd algorithm, I use the Euclidean_algorithm.
Some special cases

z = 0 is always TRUE, because we ALWAYS start from (0, 0).

z = x + y is always TRUE, because we ALWAYS end at (x, y).

When x = 0 (or y = 0), we only need to judge z = y (or z = x).

When x = y, since the light path diagram can ONLY go from (0, 0) to (0, y),and then to (x, 0) and (x, y), z MUST be 0, x, 2x.
Code
class Solution {
public:
int gcd(int a, int b)
{
if(a % b == 0)
{
return b;
}else{
return gcd(b, a % b);
}
}
bool canMeasureWater(int x, int y, int z) {
if(z == 0  z == x + y) return true;
if(z > x + y) return false;
if(x == 0) return z == y;
if(y == 0) return z == x;
if(x == y) return z == x;
int y_in = (y > x)? y : x;
int x_in = (y > x)? x : y;
int r = y_in % x_in;
if (r == 0)
{
return z % x_in == 0;
}else{
return z % gcd(r, x_in) == 0;
}
}
};