题目描述

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0，1，以及 2。

正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q。

返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。

样例

输入：p = 2, q = 1
输出：2
解释：这条光线在第一次被反射回左边的墙时就遇到了接收器 2。

注意

• 1 <= p <= 1000
• 0 <= q <= p

算法

(找规律) $O(\log p + \log q)$

1. 求出 p 和 q 的最小公倍数 lcm，令 x = lcm / p, y = lcm / q。
2. 如果 y 为奇数，则说明最终会被右墙的接收器接收，此时若 x 也为奇数，则说明是右上角，否则是右下角。
3. 如果 y 为偶数，如果题目保证了一定能被接收，则一定是左上角的接收器。

时间复杂度

• 算法核心在求最大公约数，时间复杂度为 $O(\log p + \log q)$。

空间复杂度

• 由于使用了递归辗转相处，故需要额外的 $O(\log p + \log q)$ 的栈空间。

C++ 代码

class Solution {
public:
    int gcd(int x, int y) {
        return y ? gcd(y, x % y) : x;
    }

    int mirrorReflection(int p, int q) {
        int lcm = p * q / gcd(p, q);
        int x = lcm / p, y = lcm / q;
        if (y % 2 == 1) {
            if (x % 2 == 1)
                return 1;
            return 0;
        }
        return 2;
    }
};