※ 引述《fxfxxxfxx (爱丽丝)》之铭言:
: 4. Check if Point Is Reachable
: 花了 10 秒丢一个 return gcd(x, y) == 1 试试
: 果不其然是错的
: 想了一阵子之后,发现几个性质
: 1. 不能让值变成 <= 0,不然永远回不去,因为无法让另一个也变负的
: 2. 因此想让值变大只能用 *2 的
: 3. 因此对 (X, Y) 而言,假如 X = 2 * Z
: 则 (X, Y) 是否能到达若且唯若 (Z, Y)
: 4. 因此我们可以等价的转换成都是奇数的形式
: 5. 如果都是奇数且不失一般性令 X >= Y,则
: (X, Y) 能否到达等价于 (X - Y, Y) 能否到达
: 不能减另一个方向因为会让其中一边 <= 0
: 所以可以让 (X, Y) 不断递减,
: 且每两次操作至少减半一次(第5步的 X-Y 一定是偶数)
: 所以是 O(logn) 可以解
看了别人的解才发现
最后那个X 和 Y 互减
其实根本就是在做 gcd (加速版,因为遇到偶数会除2)
所以这题其实是在问公因子是否只有 2 (或没有)
要炫技的话可以用
return __builtin_popcount(gcd(targetX, targetY)) == 1;
来一行解决 = =