SP13388题解

题意简述

给你两个桶，初始各有$x$ , $y$ 升水，每次可以从一个木桶向另一个木桶倒水，直到一个桶装满或另一个桶无剩余。判断桶内是否能达到要求水量 $y$。

题目解决

满足题意的有且仅有以下两种情况。

1. $x$ , $y$ 的最大公因数必须整除 $z$ 即 $\gcd(x,y)|z$。
2. $x$ , $y$ 中必须至少有一个大于等于 $x \ge z | y \ge z$。

证明应该是显然的。

题目实现

用拓展欧几里得算法，实现还是非常简单的。

#include<bits/stdc++.h>
using namespace std;
int T;
int exgcd(int a,int b,int &x,int &y){
	if(b==0){x=1,y=0;return a;}//特判 
	int d=exgcd(b,a%b,y,x);//d为gcd(a,c)
	y-=(a/b)*x;
	return d;
}
int main() {
	cin>>T;
	while(T--){
		int a,b,c;
		cin>>a>>b>>c;
		int x,y;
		if(a+b<c){//都装起来都不够
			cout<<"NO"<<endl;
			continue;
		}
		if(c==0){//奇妙的特判，不用倒水肯定可以 
			cout<<"YES"<<endl;
			continue;
		}
		if(a==0||b==0){//同理 
			if(b==c||a==c)cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
			continue;
		}
		int d=exgcd(a,b,x,y);//exgcd调用入口 
		if(c%d==0)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}