主題
題目連結：
題目意譯：
現在存在著一個無限大的網格。你現位於點 (1, 1)，而你需要使用有限步數到達點 (targetX, targetY)。
在每一步中，你可以從點 (x, y) 移動到下列其中一點：
(x, y - x)
(x - y, y)
(2 × x, y)
(x, 2 × y)
給定兩整數 targetX 和 targetY 代表你的最終位置的 X 軸座標以及 Y 軸座標。如果你可以從 (1, 1) 抵達該處則回傳真（True）；反之，則回傳假（False）。
限制：
1 ≦ targetX, targetY ≦ 10 ^ 9
範例測資：
範例 1：
輸入： targetX = 6, targetY = 9
輸出： false
解釋： 不可能用任意步數序列來從 (1, 1) 走到 (6, 9)，所以回傳假。
範例 2：
輸入： targetX = 4, targetY = 7
輸出： true
解釋： 你可以遵循路徑 (1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7)。
解題思維：
這題有著非常簡單的結論——只要 targetX 和 targetY 的最大公因數（Greatest Common Divisor，GCD）是 2 的某個冪次，若且唯若存在一路徑從 (1, 1) 走到 (targetX, targetY)。
以下為證明：
我們定義 P 為「targetX 和 targetY 的最大公因數是 2 的某個冪次」、Q 為「存在一路徑從 (1, 1) 走到 (targetX, targetY)」。則原命題可以寫為 P ↔ Q 之邏輯式。
首先我們證明 P → Q：
已知 targetX 和 targetY 的最大公因數為 2 ^ k，其中 k ≧ 0。則我們可以「反著走」走回 (1, 1)，也就是說原本的
(x, y - x)
(x - y, y)
(2 × x, y)
(x, 2 × y)
將變成
(x, y + x)
(x + y, y)
(x ÷ 2, y)
(x, y ÷ 2)
從 (targetX, targetY) 反著走回到 (1, 1) 的方式為下（令 (x, y) 為「現在」所處的點）：
一，每當 x 或是 y 是偶數，則將 x 或是 y 除以 2。而這只會將冪次 k 降低或者不變；
二，每當 x 和 y 都是奇數時，則將 x 變成 x + y（當 x > y 時）又或是將 y 變成 x + y（當 x < y 時）。
而因為 x 和 y 都是奇數，因此 x + y 必為偶數，因故必定會走到步驟一來除以 2。因此最後必定會將某一個座標值至少變為 (x + y) ÷ 2，而其將小於等於被更動的原本之座標值。
可以看到兩座標值之最大公因數必為 1，不論變換前或變換後。變換前很明顯，因為一開始最大公因數只由 2 的冪次組成，而步驟一會將這個冪次 k 降到 0。因此「第一次」執行步驟二時最大公因數為 1。
而假設變換後兩數為 x' 和 y' 且最大公因數變大為 q（注意到不會被 2 整除，因為我們可以先去跑步驟一來擺脫掉 2 的因數），則代表著 x' 或 y' 本來就會被 q 整除（因為固定某一個座標值不變，直到做下一次步驟二為止）。而要處理這個矛盾，q 只能是 1，也就是不變。
因此步驟二將會把其中一個座標值變小並維持最大公因數不變（但這可能需搭配著若干次步驟一）。
將以上兩個步驟統整便可以得到我們最終可以將兩個座標值的最大公因數變為 1 之後繼續將兩數變小，直到抵達 (1, 1) 為止。
而我們將從 (targetX, targetY) 反著走回到 (1, 1) 的序列反轉（即順序顛倒）並將每一步回復至
(x, y - x)
(x - y, y)
(2 × x, y)
(x, 2 × y)
之形式便可以得到從 (1, 1) 走到 (targetX, targetY) 之序列。因此 P → Q。
我們再來證明 ¬P → ¬Q（等價於證明 Q → P）：
已知 targetX 和 targetY 的最大公因數為 q × 2 ^ k，其中 k ≧ 0 、 q > 1 且 q 不被 2 整除。如上，我們先觀察試圖反著走會發生什麼事（這邊就不重複定義步驟一和步驟二）。
此時基於一樣的論述，執行步驟二可能會將最大公因數變大，但這個行為只會影響到 k 值，與 q 無關（一樣如果 q 變大了，那原本的 q 本來就應當是變大後的數字，繼而產生矛盾）。
而步驟一也同樣只跟 k 值有關。因此無論如何我們最終必定會在兩個座標值中留下至少 q 的因數。而 q > 1，因此不可能走到 (1, 1)，頂多走到 (q, q)。因此 ¬P → ¬Q。
合併兩證明便可以得到 P ↔ Q。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
