判断一个点是否可以到达

题目

2543. 判断一个点是否可以到达

---

给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。

每一步 ，你可以从点 (x, y) 移动到以下点之一：

• (x, y - x)
• (x - y, y)
• (2 * x, y)
• (x, 2 * y)

给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。

示例 1：

输入：targetX = 6, targetY = 9
输出：false
解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。

示例 2：

输入：targetX = 4, targetY = 7
输出：true
解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。

提示：

• 1 <= targetX, targetY <= 10^9

题解

方法一：

思路

我们逆向考虑从(x,y)到(1,1)。

如果只用前两种走法能让(x,y)成为(1,1)，说明x和y是互质的。

增加后两种走法后，x和y分别移除若干2因子后会互质，x和y在32位整数内，2因子个数在30左右

因此枚举即可。

代码

class Solution {
public:
    bool isReachable(int x, int y) {
        vector<int> v1, v2;
        while (x%2==0) v1.push_back(x), x/=2;
        while (y%2==0) v2.push_back(y), y/=2;
        if (x == 1 || y == 1) return true;
        v1.push_back(x), v2.push_back(y);
        for (int i:v1) {
            for (int j:v2) {
                if (gcd(i,j) == 1) return true;
            }
        }
        return false;
    }
};

方法二：

思路

x和y的最大公约数是2的幂次。

若最大公约数是2的幂次，可以通过3，4种操作的逆操作，使得x和y互质。接下来用1，2种操作的逆操作，变为(1,1)

代码

class Solution {
public:
    bool isReachable(int x, int y) {
        int t = gcd(x, y);
        while (t%2 == 0) t>>=1;
        return t == 1;
    }
};