扩展欧几里得算法的应用

LeetCode 水壶问题

有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。

你允许：

装满任意一个水壶

清空任意一个水壶

从一个水壶向另外一个水壶倒水，直到装满或者倒空

样例：　x=3, y=5, z=4 true,

因为4 % gcd(3,5) == 4 % 1 == 0

问题可以转化为a*x + b*y = z

思路：若a,b的最大公约数为gcd(a,b)，则z会是gcd(a,b)的整数倍！

恰好利用欧几里得的扩展定理

int gcd(int a, int b){
      return b == 0 ? a : gcd(b,a%b);
  }
  bool canMeasureWater(int x, int y, int z) {
      return (z == 0 || (x+y >= z && z % gcd(x,y) == 0));
  }

FEATURED TAGS

FRIENDS