LeetCode 780. Reaching Points

题目链接：https://leetcode.com/problems/reaching-points/

题意：给定操作可以使点(x,y)变为点(x+y,y)或者点(x,x+y)。现已知初始点(sx,sy)和目标点(tx,ty)，问是否能使用该变换使得(sx，sy)变为(tx,ty)。变换次数不限。(1leq sx,sy,tx,ty leq1e9)

最简单的方法是BFS，但是数据范围BFS会超时，当tx大于sx时，应该不断从tx中减去ty直到tx不大于sx或者tx不大于ty。反之如果ty比tx大亦然。

class Solution {
public:
	bool reachingPoints(int sx, int sy, int tx, int ty) {
		int cnt = 0;
		while (tx-sx>=ty||ty-sy>=tx) {
			if (tx>ty&&tx>sx) 
				tx = tx-(tx - sx)/ ty*ty;
			if (ty>tx&&ty>sy) 
				ty = ty - (ty - sy)/ tx * tx ;
		}
		return tx == sx&&ty == sy;
	}
};