---
# System prepended metadata

title: 0780. Reaching Points
tags: [Leetcode, Hard, Math]

---

# 0780. Reaching Points
###### tags: `Leetcode` `Hard` `Math`
Link: https://leetcode.com/problems/reaching-points/
## 思路
如果我们从source往下找target 有很多种情况要考虑(可以想象成一个tree)
但是如果我们从target往上考虑会发现只有一条路径 因为所有值都是整数 所以如果```x>y``` parent node就是```(x-y, y)``` 反之就是```(x, y-x)```
但如果一点一点减就会TLE
所以就要想到取余数的方法 但取余数的方法有一个问题是有可能一下子减的太多了 例如target是(2,1) source是(1,1)
如果我们直接写成
```
if(tx>ty) tx%=ty;
else ty%=tx
```
target就会直接变成(0,1)
所以我们做了改进
如果```ty>sy``` 也就是```ty```还会再改变 这时候我们只要让```tx%=ty```就可以 因为我们知道```ty```还需要再减小 所以```tx```一定要变到比```ty```小 我们才能在下一步```ty-tx```
如果```ty<=sy``` 也就是```ty```不会再改变了 只要改变```tx```就好 那我们只需要判断```(tx-sx)%ty==0```
这时候可能会问为什么不判断```ty<sy```因为它也会让答案不成立 但实际上我们已经在最外层的回圈保证```ty>=sy```了
## Code
```java=
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while(tx>=sx && ty>=sy){
            if(tx==sx && ty==sy) return true;
            if(tx>ty){
                if(ty>sy) tx%=ty;
                else return (tx-sx)%ty==0;
            }
            else{
                if(tx>sx) ty%=tx;
                else return (ty-sy)%tx==0;
            }
        }
        return tx==sx && ty==sy;
    }
}
```