0780. Reaching Points¶
题目信息¶
- 题号:
0780
- 难度:
Hard
- 主题:
坐标、可达性、整数变换
- 原题:
- 重点:
每次只能把一个坐标替换为两坐标之和,即
(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,因此不可能到达。