※ 引述《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;
來一行解決 = =
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674318369.A.61B.html