SPOJ BTCODE_A - Traversing Grid

题目传送门

简单妙妙题。

题意

有四种点的变换，分别是把点 $(x,y)$ 变成 $(y,x),(x,-y),(x+y,y),(2\cdot x,y)$。

给定起点 $(x_s,y_s)$ 和终点 $(x_d,y_d)$，问能否通过若干次变换将起点变为终点。

题解

结论：答案为 Yes 当且仅当 $\gcd(x_s,y_s)\cdot 2^k=\gcd(x_d,y_d)$。

容易发现，除了第四种变换，其他三种变换后 $\gcd(x,y)$ 都不变，而第四种变换后 $\gcd(x,y)$ 最多 $\times 2$。所以最后 $\gcd(x,y)$ 只能是乘上一个 2 的整数次幂。这样我们就证明了必要性。

接下来证明充分性：发现前三项其实做的就是辗转相减，所以最后一定可以变成 $(\gcd(x_s,y_s),0)$。再经过若干次变换 4，可以变成 $(\gcd(x_d,y_d))$。
又可以发现，四种操作全都可逆，所以可以逆着辗转相减，最后就能变成 $(x_d,y_d)$。

于是就证明了结论是充要的。

Code

bool check(ll x, ll y) {
    for (ll p = 1;x * p <= y;p *= 2ll) {
        if (x * p == y)return 1;
    }
    return 0;
}
void solve() {
    cin >> a >> b >> c >> d;
    if (a == 0 && b == 0) {
        if (c == 0 && d == 0)cout << "YES\n";
        else cout << "NO\n";
        return;
    }
    if (c == 0 && d == 0) {
        cout << "NO\n";
        return;
    }
    e = __gcd(abs(a), abs(b)), f = __gcd(abs(c), abs(d));
    if (f % e == 0 && check(e, f))cout << "YES\n";
    else cout << "NO\n";
}