CF1612D. D. X-Magic Pair

题目大意

给出\(t\)组数据，每组数据给出\(a,b,x\)三个数

对于\(a,b\)，可以分别作出两种操作

\(a := |a - b|\)

\(b := |a - b|\)

求问，能否通过一系列操作，使\(a,b\)最终的数值满足\(a = x\) 或 \(b = x\)

如果可以满足，输出YES，否则输出NO

解题思路

为了方便解题，我们使 \(a,b\) 始终满足 \(a > b\)

对于一对 \(a,b\) ，考虑对 \(a\) 进行操作，如果此时能通过若干次操作，使得要求被满足，那么我们可以记作 \(a - p * b = x\)，要使得一个正整数\(p\)存在，需要满足 \(\left\{\begin{array} xx \%b = a\%b\\ x <=a\end{array}\right.\) ，当方程组被满足时，说明有解。

如果此时无解，我们可以对余下的数继续进行操作，这就相当于对 \(b , a\%b\) 这一对数继续进行求解。这一部分我们可以通过递归来实现。

过程中需要对 \(b = 0\) 的情况进行特判，此时当且仅当 \(x = a\) 时，有解

代码

#include
using namespace std;
using ll = long long;
ll f(ll a, ll b, ll x) {
	if (b == 0)
		return x == a;
	if (x <= a && x % b == a % b)
		return 1;
	return f(b, a % b, x);
}

void solve() {
	ll a, b, x;
	cin >> a >> b >> x;
	if (a < b)
		swap(a, b);
	if (f(a, b, x))
		cout << "YES\n";
	else
		cout << "NO\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}