1. Compute g = gcd(p, q) 2. Reduce: p = p / g, q = q / g 3. Now p and q are coprime 4. If p is odd and q is odd: return 1 (northeast corner) 5. If p is odd and q is even: return 0 (southeast corner) 6. If p is even and q is odd: return 2 (northwest corner) (p even and q even is impossible since they are coprime)
題目描述： 有一個正方形房間，邊長為 p。房間四面都是鏡子。西南角為原點，一道光線從西南角出發，先射向東邊牆壁上高度為 q 的點。光線會在鏡面間反射。在東邊牆壁上，角落 0（東南角）、角落 1（東北角），在西邊牆壁上角落 2（西北角）有感應器。問光線最先到達哪個感應器。
解題思路：
時間複雜度：O(log(min(p, q))) — 計算 GCD 的時間
空間複雜度：O(1) — 只用常數空間
模擬反射：直接模擬光線的反射過程。維護光線位置和方向，每次碰到牆壁就反射。在碰到感應器位置時停止。時間複雜度 O(p/gcd(p,q))，對於 p 和 q 互質時可能很慢。
LCM 方法：直接計算 lcm(p, q)，然後判斷 lcm/p 和 lcm/q 的奇偶性。與 GCD 方法等價，但可能更容易理解「光線要走多遠才到達角落」。