CF1612D X-Magic Pair 题解

思路

我们首先假定 \(a < b\) ，那么我们可以通过题目给定的方式将 \((a,\,b)\) 转移到：

• \((b - a,\,b)\)
• \((a,\,b- a)\)

这是显然的。但是我们发现如果我们转化为 \((b - a,\, a)\)，那么下一步就会转移到：

• \(((b - a) - (b - a),\, a) = (0,\,a)\)
• \((b - a,\, a - (b - a)) = (b -a,\, 2a - b)\)

很显然这两种情况都是相当复杂且并不优的，于是我们只考虑转移到 \((a,\, b - a)\) 的情况。

在这种情况中，如果一直转换，就会变成 \((a,\,b - ka)\)，其中 \(k \in \mathbb{Z}^+\)。

知道了转移方式，我们就只需要判断 \(b - ka = x\) 或者 \(a = x\) 即可，而 \(b - ka = x\) 又可以被表达为 \(b - x \equiv 0 \pmod a\)，使得判断更为简单。此后类似辗转相除的递归 \((b \bmod a, a)\) 判断即可。

代码

#include <iostream>

#define int long long

using namespace std;

int t, a, b, x;

bool check(int a, int b, int x) {
	if (b < a) {
		swap(a, b);
	}
	if (a <= 0 || b <= 0 || b < x) {
		return false;
	}
	if (a == x || (b - x) % a == 0) {
		return true;
	}
	return check(b % a, a, x);
}

signed main() {
	cin >> t;
	while (t--) {
		cin >> a >> b >> x;
		if (b < a) {
			swap(a, b);
		}
		if (check(a, b, x)) {
			cout << "YES\n";
		} else {
			cout << "NO\n";
		}
	}
}