有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
示例 1: (From the famous “Die Hard” example)

输入: x = 3, y = 5, z = 4
输出: True

示例 2:

输入: x = 2, y = 6, z = 5
输出: False

思路分析

这道题可以完全转化为裴蜀定理。

在数论中，裴蜀定理是一个关于最大公约数 (或最大公约式) 的定理。

裴蜀定理

对任意两个整数 a、b，设 d是它们的最大公约数。那么关于未知数 x和 y的线性丢番图方程（称为裴蜀等式）：

ax+by=m

有整数解 (x,y) 当且仅当 m是 d的整数倍。裴蜀等式有解时必然有无穷多个解。

以题目给的例子x = 3, y = 5, z = 4，我们其实可以表示成3 3 - 1 5 = 4, 即3 x - 1 y = z。我们用 A 和 B分别表示3升的水壶和5升的水壶。那么我们可以：

倒满A（1）
将 A 倒到 B
再次倒满 A（2）
再次将 A 倒到 B（A这个时候还剩下1升）
倒空 B（-1）
将剩下的1升倒到 B
将 A 倒满（3）
将 A 倒到 B
B 此时正好是4升
上面的过程就是3 x - 1 y = z的具体过程解释。

贝祖定理告诉我们，ax + by = z 有解当且仅当 z 是 x, y 的最大公约数的倍数。因此我们只需要找到 x, y 的最大公约数并判断 z 是否是它的倍数即可.

image.png

  1. /**
  2.  * @param {number} jug1Capacity
  3.  * @param {number} jug2Capacity
  4.  * @param {number} targetCapacity
  5.  * @return {boolean}
  6.  */
  7. var canMeasureWater = function(jug1Capacity, jug2Capacity, targetCapacity) {
  8.   const x = jug1Capacity, y = jug2Capacity, z = targetCapacity
  9.   if (x + y < z) return false;
  11.   if (z === 0) return true;
  13.   if (x === 0) return y === z;
  15.   if (y === 0) return x === z;
  17.   function GCD(a, b) {
  18.     let min = Math.min(a, b);
  19.     while (min) {
  20.       if (a % min === 0 && b % min === 0) return min;
  21.       min--;
  22.     }
  23.     return 1;
  24.   }
  26.   return z % GCD(x, y) === 0;
  27. };