ACM模版

描述

题解

神级模拟推导题……经过模拟推导可以推出：

(a, b) -> (b, a) ··············································(1)
if (a, b) -> (x, y) to (x, y) -> (a, b) ··········(2)

那么我们可以逐次推导出(假设a>b)：

(a, b) -> (a - b, b) -> (a - 2b, b) -> … -> (a - nb, b) 其中，n = a / b
(a, b) - > (a % b, b) -> (b, a % b)
由此可以联想到欧几里得算法求解最大公约数！
如果(a, b)的最大公约数是c，那么(a, b)一定可以达到(c, c)
当(x, y)的最大公约数也是c时，说明(x, y)也可以到达(c, c)
如此，说明两者存在路径连通，输出”Yes”；反之输出”No”

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

typedef long long ll;
using namespace std;

ll kgcd(ll a, ll b)
{
    if (!a)
    {
        return b;
    }
    else if (!b)
    {
        return a;
    }
    else if (!(a & 1) && !(b & 1))
    {
        return kgcd(a >> 1, b >> 1) << 1;
    }
    else if (!(b & 1))
    {
        return kgcd(a, b >> 1);
    }
    else if (!(a & 1))
    {
        return kgcd(a >> 1, b);
    }
    else
    {
        return kgcd(abs(a - b), min(a, b));
    }
}

int main(int argc, const char * argv[])
{
    int T;
    cin >> T;

    ll a, b, x, y;
    while (T--)
    {
// scanf("%lld %lld %lld %lld", &a, &b, &x, &y);
        cin >> a >> b >> x >> y;
        if (kgcd(a, b) == kgcd(x, y))
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }

    return 0;
}

参考

《GCD》