Leetcode 365 - Water and Jug Problem（裴蜀定理）

题意

jug PRoblem，给2个罐子，容积为x和y，给定整数z，问能否用x和y凑出z的水。

可做的：

思路

如果求最短步数可以通过bfs来做，这道题只需要判断能否有解。

其中步骤3是水在x和y之间流通并不会造成损失，而步骤1和2可以列出如下方程：

mx+ny=z$mx + ny = z$

即我们要做的就是判断是否有解。

根据裴蜀定理，我们只需要判断z是否是x和y的最大公约数g的整数倍即可。

并且还需要满足x+y≥z$x + y /geq z$

代码