LeetCode365.水壶问题

这题我只会数学解法，太菜了😭

其实第一眼没有思路，瞄了一眼标签是“数学”，就开始推公式
假设容量为x升的水壶进行了a次操作，容量为y升的水壶进行了b次操作，最终两水壶中的水总共是z升。可以得到公式：

$$\ a \times \ x + \ b \times \ y = z$$

emm，好眼熟的公式，好像是斐蜀定理。。。

斐蜀定理

对于任意正整数a，b，那么一定存在非零整数x，y，使得$a \times x + b \times y = gcd(a,\ b)$

再扩展一下，对于这道题的方程$a \times x + b \times y = z，$
当且仅当$z\ |\ gcd(x,\ y)$时该二元不定方程才有整数解。因此这道题就可以解决了。
也就意味着当$x \ + \ y \ge \ z$时应满足：$z \ mod\ gcd(x,\ y)=0$，OK了。

代码：

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
bool canMeasureWater(int x, int y, int z) {
    if(!x || !y)
    {
        if(x == z || y == z) return true;
        else return false;
    }
        if(x + y < z) return false;
        return !(z % gcd(x, y));
}

好像还有BFS的解法，打算再看一下。