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";
        }
    }
}