WaterJugProblem来源：https://leetcode-cn.com/problems/water-and-jug-problem/有两个容量分别为x升和y升的水罐，还有无限量的水。请判断用这两个水壶能否恰好得到z升水？最后，如果可以的话，使用上面的一个或两个水壶来装你得到的z升。您允许：装满任何水罐清空任何水罐将水从一个水罐倒入另一个水罐，直到满或空示例1：（来自著名的“虎胆龙威”示例）输入：x=3,y=5,z=4输出：True示例2：输入：x=2,y=6,z=5输出：False解题思路：裴树定理裴树定理是一个关于最大公约数的定理。对于任意整数a、b和m，d是a和b的最大公约数，关于未知数x和y的线性不定方程：$$ax+by=m$$有整数解当且仅当m是a和b的最大公约数的倍数。审题可得：其实每次操作都可以认为是将锅中的水总量增加x，增加y，减少x，减少y。这就涉及到锅里的水不是空的情况，所以上面的结论显然是不成立的。别着急，这里有解释：比如1，题目给出x=3，y=5，z=4。试试如何弄到一个能装4升水的水壶。（这里把能装x升水的锅设成A，能装y升水的锅设成B，形如(0,0)，表示两个锅里的水。)先装B，然后是两盆盛水的情况：(0,5)；将B锅中的水倒入A中，两锅情况：(3,2)；把A锅里的水倒掉，两锅的情况：(0,2)；将B锅中的水再次倒入A锅中，此时：(2,0)；填满锅B，此时两锅的情况：(2,5)；把锅里的水倒入A，直到满了，此时：（3、4）。此时B锅中的水为4升，就是得到的结果。在这里，我们可以观察到，在运行过程中，不会出现两个锅同时有水又不满的情况。此外，装满未满的水壶也没有意义。假设往一个没满的锅里注水时，如果另一个锅是满的，那么这种情况相当于在初始状态下直接把两个锅都注满；如果另一个罐子是空的，那么这相当于直接在初始状态下，将当前罐子装满水。同样，从未满的水壶中倒出水也没有意义。假设将一个未满的锅中的水倒掉，如果另一个锅是满的，这种情况相当于在初始状态下直接将另一个锅注满水；回到初始状态。所以这里我们可以明确之前的结论：每次操作，水的总量只会带来x或者y的变化。现在我们把问题转化为求一对整数a，b，使得$$ax+by=z$$，只要满足$z\leqx+y$，就说明目标可用。注意这里和上面裴树定理的公式不同，其中a,b代表需要的目标，x,y是已知的。（正好与裴树定理相反）。由题可知：当$a\geq0,b\geq0$时，可以得到目标；当$a<0$时，需要进行如下操作：（继续使用上面的A锅，B锅）先去B锅加水；将B壶中的水倒入A壶中；这时，如果B锅里还有水，就说明A锅满了。将A壶中的水倒掉，将B壶中剩余的水倒入A壶中。重复上述操作，直到A壶倒空a次，B壶倒b次。当$b<0$时，和上面的情况类似，只是把A锅和B锅的操作调换一下。根据裴树定理，$ax+by=z$有解当且仅当z是倍数x,y的最大公约数。所以我们只需要找到x和y的最大公约数，然后判断z是否是这个最大公约数的倍数即可得到答案。代码实现类解决方案：defcanMeasureWater(self,x:int,y:int,z:int)->bool:importmathifx+y
