前言
持续更新了
正文
问题来源
本问题来自leetcode上的365题。
问题描述
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
示例 1:
输入: x = 3, y = 5, z = 4
输出: True
示例 2:
输入: x = 2, y = 6, z = 5
输出: False
分析：
贝祖定理 对任何整数 a、 b和 m，关于未知数 x和 y的线性不定式方程 a * x + b * y = m，有整数解时当且仅当 m是 a及 b的最大公约数 d的倍数。
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func canMeasureWater(x int, y int, z int) bool {
if x + y < z {
return false
}
if x == 0 || y == 0 {
return z == 0 || x + y == z
}
return z % gcd(x, y) == 0
}
总结：
勤思考。
结语
不管怎么样好好加油。
