出题人题解｜分配水源

题目大意

每次只允许使用指定的两个容器进行称量，能否精确测量出每个家庭所需的水量。（容器间转换产生的误差忽略不计）

题意分析

在该题的条件下，我们需要通过容量分别为 A 和 B 的两个容器通过不停的装水和倒水策略准确地测量出 C 的剂量。

解题思路

对于任意两个整数 $a$ 和 $b$，他们的最大公约数 $gcd(a, b)$ 可以表示为 $gcd(a, b) = x \cdot a + y \cdot b$ 。

那么，如果我们想要用 $a$ 和 $b$ 表示一个整数 $c$ ，则 $c$ 必须是 $a$ 和 $b$ 的最大公约数的倍数。

故能够准确测量出 C 的剂量取决于以下两点：

1. C 必须小于等于 A+B，能测量的剂量最多等于两个容器容量之和
2. C 必须是 A 和 B 的最大公约数的倍数

时间复杂度解析

$gcd(a, b)$ 的时间复杂度为 $O(log(min(a, b)))$，因此程序时间复杂度为 $O(N \cdot log(min(a, b)))$

代码演示

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

void solve(){
	LL a, b, c;
	cin >> a >> b >> c;
	LL gcd_ab = __gcd(a, b);
	// a + b 可能会爆 int, 需要开 long long
	if(a + b >= c && c % gcd_ab == 0){
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

int main(){
	int n;
	cin >> n;
	while(n -- ) solve();
	return 0;
}