水蓝络合物的博客

title: X-Magic Pair date: 2022-02-01 17:04:05 tags: - 数论

题目大意

给定三个正整数\(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) (b - 2a, b - a)$ 无法继续产生新变化变化。

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

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

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/01/30/Codeforces-1612-D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！