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。

自建示例

经过多次交替变化到达目标:

输入:sx = 2, sy = 3, tx = 13, ty = 8
输出:true
解释:(2,3) 可以依次变为 (5,3)、(5,8)、(13,8),因此目标可达。

坐标的公共因子不一致:

输入:sx = 2, sy = 4, tx = 5, ty = 9
输出:false
解释:两种操作都不会改变两个坐标的最大公约数;起点坐标的最大公约数为 2,目标坐标的最大公约数为 1,因此不可能到达。