780. 到达终点

题目链接：780. 到达终点

这道题有点东西。从 (sx, sy) 推到 (tx, ty) 的搜索空间太大，随着变换次数增加，搜索空间指数级增长。

但是如果换个方向，从 (tx, ty) 倒推到 (sx, sy) 。每一步其实只能进行一种操作：

• 将 tx, ty 中的较大值减去较小值，因为题目中 sx, sy 都大于 $0$。

此时具有约束：

• (tx, ty) 这个点一定在 (sx, sy) 点的右上方，满足 (tx >= sx and ty > sy) or (ty >= sy and tx > sx)；
• 以 tx > ty 为例，将 tx 减去尽可能多的 ty，至少减去一个 ty，使得到的 tx 更小；
• 若 tx == ty，那除非 tx == ty == sx == sy，否则一定无法转换成功，因为题目中 sx, sy 都大于 $0$，经过至少 1 次转换的 tx' 和 ty' 必定不相等。

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while (tx >= sx and ty > sy) or (ty >= sy and tx > sx):
            if tx > ty:
                tx -= (tx - sx) // ty * ty or ty
            else:
                ty -= (ty - sy) // tx * tx or tx

        return ty == sy and tx == sx