LeetCode 365. 水壶问题

365. 水壶问题

题目链接-365. 水壶问题

解题思路
裴蜀定理

• 裴蜀等式：若$a,b$a,b是整数,且$gcd(a,b)=d$gcd(a,b)=d，那么对于任意的整数$x,y$x,y,$ax+by$ax+by都一定是$d$d的倍数，特别地，一定存在整数$x,y$x,y，使$ax+by=d$ax+by=d成立
• 显然，判断$z$z是否是$x$x,$y$y最大公因数的倍数即可
• 注意$z$z小于$0$0和$z$z大于$x+y$x+y的情况
• 具体操作见代码

附上代码
核心算法

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(z<0||z>x+y)
            return 0;
        if(x==0||y==0)
            return z==(x+y)||z==0;
        return z%__gcd(x,y)==0;
    }
};