【Codeforces】1612D X-Magic Pair 题解

题目大意

给定三个正整数 $a, b, x$（$1 \le a, b, x \le 10^{18}$），对 $a, b$ 进行两种操作：

• $a = |a - b|$
• $b = |a - b|$

问是否可以通过任意次这两种操作使得 $a = x$ 或者 $b = x$？

题目链接

思路

假设 $a < b$，我们推一下 $(a, b)$ 可以有哪些变化，我们要尽量用有规律的方式去枚举出所有可能变化。

1. $(a, b) \Leftrightarrow (b - a, b)$，然后就无法继续产生新变化了。
2. $(a, b) \Rightarrow (a, b - a)$。那么接下来有两种变化：
   • 2.1：$a > b - a$。$(a, b - a) \Rightarrow (2a - b, b - a)$，可继续产生新变化。
     $(a, b - a) \Leftrightarrow (a, 2a - b)$，无法继续产生新变化。
   • 2.2：$a < b - a$。$(a, b - a) \Rightarrow (a, b - 2a)$，可继续产生新变化。（标记为 #）
     $(a, b - a) \Leftrightarrow (b - 2a, b - a)$，无法继续产生新变化。

通过这种方式，我们就能不断地去枚举出所有可能达到的数，但是如果一步一步地去做，那么会超时。

对于 2.2# 的那一步，假设 $b’ = b - c \cdot a$，那么显然当 $a < b - c \cdot a$ 时，会一直执行该操作。而选择 2.2 的另外一步骤，也不会产生新的数，所以我们可以直接跳过这个步骤直接让 $(a, b - a) \Rightarrow (a, b \bmod a)$，并检验一下是否产生了答案，即判断 $(b - x) \bmod a = 0$？

#include <cstdio>
#include <iostream>
using namespace std;

int T;
long long a, b, x;

int main()
{
    scanf("%d", &T);
    while(T--) {
        bool succ = false;
        scanf("%lld%lld%lld", &a, &b, &x);
        while(a && b) {
            if(a > b)
                swap(a, b);
            a = min(a, b - a); //确保 a < b - a (其实本质上就是简略了步骤1)
            if(a == x || b == x) {
                succ = true;
                break;
            }
            if(x > b || (x < b && x > b - a) || a == 0)
                break;
            if((b - x) % a == 0) {
                succ = true;
                break;
            }
            b %= a;
        }
        if(succ)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}