0780. Reaching Points ======================================================================================================================== 题目信息 -------- :题号: 0780 :难度: Hard :主题: 坐标、可达性、整数变换 :原题: `LeetCode 0780 `_ :重点: 每次只能把一个坐标替换为两坐标之和,即 ``(x,y)`` 变为 ``(x,x+y)`` 或 ``(x+y,y)``;判断能否从指定起点精确到达目标点 题目重述 -------- 给定起点 ``(sx, sy)`` 和目标点 ``(tx, ty)``,四个坐标都为正整数。 从任意当前点 ``(x, y)`` 出发,一次操作只能选择以下一种变化:保持 ``x`` 不变并把 ``y`` 变为 ``x + y``,得到 ``(x, x + y)``;或保持 ``y`` 不变并把 ``x`` 变为 ``x + y``,得到 ``(x + y, y)``。 请判断能否经过零次或多次操作,从起点精确到达目标点。``1 <= sx, sy, tx, ty <= 10^9``。 自建示例 -------- 经过多次交替变化到达目标: .. code-block:: text 输入:sx = 2, sy = 3, tx = 13, ty = 8 输出:true 解释:(2,3) 可以依次变为 (5,3)、(5,8)、(13,8),因此目标可达。 坐标的公共因子不一致: .. code-block:: text 输入:sx = 2, sy = 4, tx = 5, ty = 9 输出:false 解释:两种操作都不会改变两个坐标的最大公约数;起点坐标的最大公约数为 2,目标坐标的最大公约数为 1,因此不可能到达。