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 <= 109

比赛时的想法

下文用 g 表示最大公约数。

• 前两个移动很像辗转相除法（这个套路在 Codeforces 上已经出烂了），g 不变；
• 后两个移动可以让 g 乘上 2^k。

而一开始 1,1 的 g=1，那么最终 targetX},\textit{targetY 的 g 只能是 2^k。

根据 231. 2 的幂 ，用 g&(g-1) 是否为 0 来判断 g 是否为 2^k。

如何构造出具体的移动方案？

从终点倒着走，那么 (x,y) 可以移动到 (x,x+y),(x+y,y),(x/2,y),(x,y/2) 这些位置，后两个移动只有偶数才能除以 2。

不断循环直到 x=y 且均为奇数（此时无法移动）：

• 只要有偶数就除以 2。
• 如果都为奇数，比如 x<y，那么走两步可以得到 (x,(x+y)/2)，这里修改 y 是因为 x<(x+y)/2<y。

那么总是可以让 x 和 y 不断变小。循环结束时如果 x=y=1，则说明可以做到。

附：视频讲解

[sol1-Python3]

class Solution:
    def isReachable(self, targetX: int, targetY: int) -> bool:
        g = gcd(targetX, targetY)
        return (g & (g - 1)) == 0

[sol1-Java]

class Solution {
    public boolean isReachable(int targetX, int targetY) {
        int g = gcd(targetX, targetY);
        return (g & (g - 1)) == 0;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }
}

[sol1-C++]

class Solution {
public:
    bool isReachable(int targetX, int targetY) {
        int g = gcd(targetX, targetY);
        return (g & (g - 1)) == 0;
    }
};

[sol1-Go]

func isReachable(targetX, targetY int) bool {
	g := gcd(targetX, targetY)
	return g&(g-1) == 0
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

复杂度分析

• 时间复杂度：O(\log(\min(\textit{targetX}, \textit{targetY})))。
• 空间复杂度：O(1)，仅用到若干变量。