> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/780.-reaching-points.md).

# 780. Reaching Points

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

```cpp
/*
 * @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
```