题目如下：
A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y). Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False. Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5) Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True Note:
sx, sy, tx, ty will all be integers in the range [1, 10^9].
解题思路：看到sx,sy,tx,ty的最大值可以是10^9，那就基本上放弃穷举法了。本题比较适合倒推法，例如题目中给的例子[1,1] -> [3,5]：要想得到[3,5]，那么前面的一组数组必定是[3,2] （即[3,5-3]）计算得来，而[3,2]又是从[1,2] (即[3-2,2])来的，最后推出[1,1]。 原理就是用[tx,ty]中较大值减去较小值依次计算得来。所以，很快我就写出来如下代码：
while tx > 0 and ty > 0:
if ty == tx:
ret = False
break
if ty > tx:
ty -= tx
else:
tx -=ty
if sx == tx and sy == ty:
ret = True
break
return ret
可以这段代码却被[1,1,10^9,1]的输入打败。一时间我竟然想不出更好的办法，直到第二天，脑子里才出现了“用除法代替减法”的方案。方案也很简单，如果tx > ty,那么tx可以利用除法得到一个不小于max(ty,sx)的最小数。完整代码如下：
class Solution(object):
def reachingPoints(self, sx, sy, tx, ty):
"""
:type sx: int
:type sy: int
:type tx: int
:type ty: int
:rtype: bool
"""
if sx == tx and sy == ty:
return True
ret = True
while tx > 0 and ty > 0:
if ty == tx:
ret = False
break
if ty > tx:
max_y = max(tx,sy)
div = (ty - max_y) / tx
div = max (div,1)
ty -= div * tx
else:
max_x = max(ty,sx)
div = (tx - max_x) / ty
div = max (div,1)
tx -= div * ty
if sx == tx and sy == ty:
ret = True
break
return ret