水壶问题.md

水壶问题

有两个容量分别为x升和y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好z升的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的z升水。 你允许：

• 装满任意一个水壶
• 清空任意一个水壶
• 从一个水壶向另外一个水壶倒水，直到装满或者倒空

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

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

解题思路

有一个数学定理：裴蜀定理
大概解释如下：

• 若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

假设x、y的最大公约数为m，对于x、y而言，通过多次的操作就能得到m，所以只需要判断z是否为m的倍数即可

// 递归求最大公约数
const gcd = (x, y) => {
  return y === 0 ? x: gcd(y, x%y)
}
const canMeasureWater = (x, y, z) => {
  // 瓶子容量不够
  if (x + y < z) return false;
  // 考虑瓶子为空的情况
  if (x === 0 || y === 0) {
    if (x === z || y === z) {
      return true;
    }
    return false;
  }
  const m = gcd(x, y)
  return z%m === 0
}