题目大意 每次只允许使用指定的两个容器进行称量，能否精确测量出每个家庭所需的水量。（容器间转换产生的误差忽略不计） 题意分析 在该题的条件下，我们需要通过容量分别为 A 和 B 的两个容器通过不停的装水和倒水策略准确地测量出 C 的剂量。 解题思路 对于任意两个整数 aaa 和 bbb，他们的最大公约数 gcd(a,b)gcd(a, b)gcd(a,b) 可以表示为 gcd(a,b)=x⋅a+y⋅bgcd(a, b) = x \cdot a + y \cdot bgcd(a,b)=x⋅a+y⋅b 。 那么，如果我们想要用 aaa 和 bbb 表示一个整数 ccc ，则 ccc 必须是 aaa 和 bbb 的最大公约数的倍数。 故能够准确测量出 C 的剂量取决于以下两点： 1. C 必须小于等于 A+B，能测量的剂量最多等于两个容器容量之和 2. C 必须是 A 和 B 的最大公约数的倍数 时间复杂度解析 gcd(a,b)gcd(a, b)gcd(a,b) 的时间复杂度为 O(log(min(a,b)))O(log(min(a, b)))O(log(min(a,b)))，因此程序时间复杂度为 O(N⋅log(min(a,b)))O(N \cdot log(min(a, b)))O(N⋅log(min(a,b))) 代码演示