---

0858. 镜面反射

• 标签：几何、数学、数论
• 难度：中等

题目链接

• 0858. 镜面反射 - 力扣

题目大意

描述：

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

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

要求：

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

说明：

• $1 \le q \le p \le 10^{3}$。

示例：

• 示例 1：

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

• 示例 2：

输入：p = 3, q = 1
输入：1

解题思路

思路 1：数学 + 最大公约数

这道题要求计算激光在正方形房间中经过镜面反射后最先遇到的接收器编号。

关键观察：

• 可以将镜面反射问题转换为"展开"问题：将房间沿着镜面展开，激光沿直线传播。
• 激光从 $(0, 0)$ 出发，斜率为 $\frac{q}{p}$，最终会到达某个点 $(m \times p, n \times q)$，其中 $m$ 和 $n$ 是整数。
• 需要找到最小的 $m$ 和 $n$，使得 $(m \times p, n \times q)$ 对应某个接收器。

接收器位置：

• 接收器 $0$：东南角 $(p, 0)$，对应 $m$ 为奇数，$n$ 为偶数。
• 接收器 $1$：东北角 $(p, p)$，对应 $m$ 和 $n$ 都为奇数。
• 接收器 $2$：西北角 $(0, p)$，对应 $m$ 为偶数，$n$ 为奇数。

算法步骤：

1. 计算 $p$ 和 $q$ 的最大公约数 $g$。
2. 化简 $m = \frac{p}{g}$，$n = \frac{q}{g}$。
3. 根据 $m$ 和 $n$ 的奇偶性判断接收器编号。

思路 1：代码

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        from math import gcd
        
        # 计算最大公约数
        g = gcd(p, q)
        
        # 化简
        m = p // g  # 水平方向的反射次数
        n = q // g  # 垂直方向的反射次数
        
        # 根据奇偶性判断接收器编号
        if m % 2 == 1 and n % 2 == 1:
            return 1  # 东北角
        elif m % 2 == 1 and n % 2 == 0:
            return 0  # 东南角
        else:  # m % 2 == 0 and n % 2 == 1
            return 2  # 西北角

思路 1：复杂度分析

• 时间复杂度：$O(\log \min(p, q))$，计算最大公约数的时间复杂度。
• 空间复杂度：$O(1)$，只使用常数额外空间。