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⁹

解法

方法一：数学

思考

从 \((1,1)\) 出发，可把当前点变为 \((x+y,y)\)、\((x,x+y)\) 或把某一坐标翻倍。坐标可达 \(10^9\)，不能搜索。

前两种移动不改变 \(\gcd\)，后两种只把 \(\gcd\) 乘上 \(2\) 的幂，故终点的 \(\gcd\) 必须是 \(2\) 的幂。反之，从终点反复除二并把较大奇数换成 \((\textit{x}+\textit{y})/2\) 可一直缩小到 \((1,1)\)。因此判断 \(\gcd(x,y)\) 是否为 \(2\) 的幂即可，即 \(x\&(x-1)=0\)。

我们注意到，前两种移动方式不会改变横、纵坐标的最大公约数，而后两种移动方式可以使得横、纵坐标的最大公约数乘上 \(2\) 的幂次。也就是说，最后的横、纵坐标的最大公约数必须是 \(2\) 的幂次。最大公约数不是 \(2\) 的幂次，那么就无法到达。

接下来，我们证明，任意满足 \(gcd(x, y)=2^k\) 的 \((x, y)\) 均可达。

我们将移动方式反转一下，即从终点往回走，那么 \((x, y)\) 可以移动到 \((x, x+y)\), \((x+y, y)\), \((\frac{x}{2}, y)\) 和 \((x, \frac{y}{2})\)。

只要 \(x\) 或 \(y\) 是偶数，我们就将其除以 \(2\)，直到 \(x\) 和 \(y\) 均为奇数。此时，若 \(x \neq y\)，不妨设 \(x \gt y\)，那么 \(\frac{x+y}{2} \lt x\)。由于 \(x+y\) 是偶数，我们可以通过操作从 \((x, y)\) 移动到 \((x+y, y)\)，再移动到 \((\frac{x+y}{2}, y)\)。也就是说，我们总能让 \(x\) 和 \(y\) 不断变小。循环结束时，如果 \(x=y=1\)，说明可以到达。

时间复杂度 \(O(\log(\min(targetX, targetY)))\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

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

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

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

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

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

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

function isReachable(targetX: number, targetY: number): boolean {
    const x = gcd(targetX, targetY);
    return (x & (x - 1)) === 0;
}

function gcd(a: number, b: number): number {
    return b == 0 ? a : gcd(b, a % b);
}

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

题目描述

解法

方法一：数学

评论