[LeetCode]365. Water and Jug Problem

https://leetcode.com/problems/water-and-jug-problem/#/description

给两个杯子容量分别是x和y，判断能否量出容量z

假设最终体积z = m * x + n * y（m与n为整数，可以为0或者为负） 令x = p * gcd, y = q * gcd，可知p与q互质。 则z = (m * p + n * q) * gcd 可以证明一定存在m, n，使得m * p + n * q = 1（p与q互质的性质，参见：裴蜀定理） 由此可知z一定是gcd的整数倍

public class Solution { public boolean canMeasureWater(int x, int y, int z) { if (x + y < z) { return false; } if (x == z || y == z || x + y == z) { return true; } return z % gcd(x, y) == 0; }   private int gcd(int a, int b) {      if (a == 0) {         return b;      }      return gcd(b % a, a);   } }