解題說明
Mirror Reflection
題目描述： 有一個正方形房間，邊長為 p。房間四面都是鏡子。西南角為原點，一道光線從西南角出發，先射向東邊牆壁上高度為 q 的點。光線會在鏡面間反射。在東邊牆壁上，角落 0（東南角）、角落 1（東北角），在西邊牆壁上角落 2（西北角）有感應器。問光線最先到達哪個感應器。
解題思路：
- 展開鏡面：不把光線想成在鏡面間反射，而是把房間展開（像瓷磚一樣排列），光線變成直線行進。
- 光線每次水平走 p、垂直走 q。我們需要找到最小的 k，使得 k*q 是 p 的整數倍（即光線恰好到達角落）。
- kq = mp，即 k*q/p 為整數。最小 k = p / gcd(p, q)，此時 m = q / gcd(p, q)。
- 判斷到達哪個感應器：m 的奇偶決定在東/西牆，k 的奇偶決定在上/下角。
- m 為奇數, k 為奇數 → 感應器 1（東北角）
- m 為奇數, k 為偶數 → 感應器 0（東南角）
- m 為偶數, k 為奇數 → 感應器 2（西北角）
C++ 解法
複雜度分析
時間複雜度：O(log(min(p, q))) — 計算 GCD 的時間
空間複雜度：O(1) — 只用常數空間
虛擬碼
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)
其他解法
-
模擬反射：直接模擬光線的反射過程。維護光線位置和方向，每次碰到牆壁就反射。在碰到感應器位置時停止。時間複雜度 O(p/gcd(p,q))，對於 p 和 q 互質時可能很慢。
-
LCM 方法：直接計算 lcm(p, q)，然後判斷 lcm/p 和 lcm/q 的奇偶性。與 GCD 方法等價，但可能更容易理解「光線要走多遠才到達角落」。
延伸思考
- 如果房間不是正方形而是長方形，結果會有什麼變化？
- 如果在四個角落都有感應器，答案會是什麼？
- 光線在到達感應器之前，總共反射了幾次？