780. Reaching Points

https://leetcode.com/problems/reaching-points/

S = (x, y)，每次能让它变(x + y, y)或(x, x + y)，问能否最终变成T。给定起点和终点，如果从起点开始搜每次有两种action，但如果从终点往前搜每个结点其实只能有一个parent，比如(19, 12)只能是从(7, 12)变来，否则(19, y + 19 = 12)，y只能是负数了。因此从后面开始每次判断x和y哪个大，小的和parent的对应值一致，大的肯定合并而来的，让大的减去另一个就是parent了。当大的是小的很多倍时，同样的步骤就会重复很多遍，每次都要减相同的小的。连续加上同样的数是乘法，连续减去对应除法，因此直接取余，比较余数是否和sy sx之间取余的结果相同。

/*
 * @lc app=leetcode id=780 lang=cpp
 *
 * [780] Reaching Points
 */

// @lc code=start
class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (sx <= tx && sy <= ty) {
            if (tx < ty) {
                ty = ty % tx;
                if (ty == sy % sx && sx == tx) {
                    return true;
                }
            } else if (tx > ty) {
                tx = tx % ty;
                if (tx == sx % sy && sy == ty) {
                    return true;
                }
            } else {
                return sx == sy;
            }
        }
        return false; 
    }
};
// @lc code=end