Readme

2543.Check-if-Point-Is-Reachable

我们反过来思考从(x,y)走到(1,1)的操作。将原操作逆过来就是

1. (x,y)->(x+y, y)
2. (x,y)->(x, x+y)
3. (x,y)->(x/2, y) if (x%2==0)
4. (x,y)->(x, y/2) if (y%2==0)

如果我们不看第三和第四条规则，我们可以发现，从(x,y)走到任意的(a,b)，其中a必然写作mx+ny的形式。mx+ny必然含有gcd(x,y)。再考虑第三和第四条，我们只能除以2来降低数字的大小，所以如果gcd(x,y)包含非2的因子，我们是如论如何都无法除掉的，最终也不可能达到1.

那么如果gcd(x,y)不含2的次方之外的元素，那么如何证明一定能转化为(1,1)呢？方案如下：

1. 如果x和y任意一个是偶数，就将该数字除以2。
2. 如果x和y都是奇数，就转化为(x,(x+y)/2)或者((x+y)/2,y)，目的就是将数字变小。

以上两个操作都一定会将数字变小，除非x=y=odd。因为之前说过gcd(x,y)不含2的次方之外的元素，所以只有x=y=1是最终的归宿。