教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文精讲 LeetCode 0858「镜面反射」这道「几何 / 数学 / 数论」中等题以《算法通关手册》题解为主体完整还原题目背景、示例与标准解法并深入剖析其背后的「镜面展开」思想与最大公约数GCD化简原理。读完你将掌握如何把周期性反射问题转化为直线传播问题如何用一次gcd计算同时得到两个方向上的反射次数以及如何仅凭奇偶性一行定位到三个接收器中的一个从而做到 O(log min(p, q)) 时间内解出本题。题目档案与仓库位置题目编号LeetCode 0858镜像反射 / Mirror Reflection标签几何、数学、数论难度中等数据范围$1 \le q \le p \le 10^{3}$保证光线最终会遇到一个接收器本题解在仓库中的位置docs/solutions/0800-0899/mirror-reflection.md所在章节索引docs/solutions/0800-0899/index.md0858 位列其中章节按题号归档便于检索全书刷题总表docs/00_preface/00_05_solutions_list.md记录本题标签为「几何、数学、数论」难度为中等题目理解正方形房间里的激光反射题目描述有一个特殊的正方形房间每面墙上都有一面镜子。除西南角以外每个角落都放有一个接受器编号为 0、1 以及 2。正方形房间的墙壁长度为 $p$一束激光从西南角射出首先会与东墙相遇入射点到接收器 0 的距离为 $q$。要求返回光线最先遇到的接收器的编号保证光线最终会遇到一个接收器。房间布局可以用下面这张示意描述西南角无接收器其余三个角分别为接收器 2、1、0北墙 ┌─────────────┐ │ │ 西 │ 接收器 1 │ 东 墙 │ (0, p) (p,p)│ 墙 │ │ │ 接收器 0 │ │ (p, 0) │ └─────────────┘ 南墙无接收器激光从西南角 $(0,0)$ 射出斜率由 $q$ 决定——它沿东墙方向前进第一次碰到东墙时入射点与接收器 0东南角的竖直距离恰好为 $q$。注意约束 $q \le p$这说明首次触墙点落在东墙的墙面上不会在第一次就撞上角落。示例 1输入p 2, q 1 输出2 解释这条光线在第一次被反射回左边的墙时就遇到了接收器 2。示例 2输入p 3, q 1 输出1原文档中示例 2 的输出行存在笔误正确结果应为 1因为 $g \gcd(3, 1) 1$$m 3$ 为奇数、$n 1$ 为奇数对应接收器 1。解题思路把反射「展开」成直线传播为什么可以「展开」镜面反射最麻烦的地方在于每撞一次墙光线的方向就会改变追踪反射过程既容易出错又难以分析。这里的关键技巧是换一个坐标系——不去反射光线而是去反射「房间」。当激光撞上某面墙时可以想象成它穿过了这面镜子进入一个与当前房间关于该墙对称的「镜像房间」。光线本身始终沿直线前进只是我们观察到的房间被复制、翻转、拼接成了无限延伸的平面。这样原来的反射路径就被等价地描述为在铺满镜像房间的无限平面上一条从原点出发的直线。这正是题解原文档中「关键观察」的数学含义将镜面反射问题转换为「展开」问题将房间沿着镜面展开激光沿直线传播激光从 $(0, 0)$ 出发斜率为 $\frac{q}{p}$最终会到达某个网格角落点只需要找到「最小的」那个角落点就能确定最先命中的接收器。展开平面上的数学模型在展开平面上每个房间都是边长为 $p$ 的正方形墙壁就是网格线竖线 $x m \cdot p$$m \in \mathbb{Z}$与横线 $y n \cdot p$$n \in \mathbb{Z}$。激光从 $(0, 0)$ 出发斜率为 $\frac{q}{p}$因此轨迹上的点满足$$y \frac{q}{p}, x$$光线每次穿过一条竖线$x m \cdot p$就对应原房间中一次东墙/西墙上的反射每穿过一条横线$y n \cdot p$就对应一次北墙/南墙上的反射。因此$m$ 光线在展开平面上穿过的竖线数 水平方向的反射次数$n$ 光线在展开平面上穿过的横线数 垂直方向的反射次数。第一次撞上角落的数学条件激光撞上「角落」即原房间的墙角接收器所在位置等价于它在展开平面上同时到达某条竖线和某条横线的交点即坐标 $(m \cdot p,\ n \cdot p)$ 既是竖线又是横线上的点。由于激光轨迹满足 $y \frac{q}{p} x$代入交点 $(m \cdot p,\ n \cdot p)$ 可得$$\frac{n \cdot p}{m \cdot p} \frac{n}{m} \frac{q}{p}$$也就是说首次命中角落要求最小的整数对 $(m, n)$ 满足 $m : n p : q$。这正是最小公倍数视角光线第一次同时落在竖线与横线上发生在它前进到 $x$ 方向跨越了 $p$ 的「最小公倍数」个房间宽度、$y$ 方向跨越了同样个数的房间高度的时候。反射次数与最大公约数设 $g \gcd(p, q)$则 $\frac{p}{g}$ 与 $\frac{q}{g}$ 互质。将比值 $p : q$ 约分到最简就得到最小的正整数解$$m \frac{p}{g}, \qquad n \frac{q}{g}$$这两个数恰好是不可再约分的反射次数$m$ 是水平方向的反射次数$n$ 是垂直方向的反射次数。直觉上$g$ 越大意味着 $p$ 与 $q$ 的公因子越多光线能越早命中一个角落因此反射次数越少当 $p, q$ 互质$g 1$时反射次数最多。这里体现的正是数论中最大公约数的核心地位——仓库中另一道题 0365. 水壶问题 借助贝祖定理Bézouts identity说明「能测量的水量必须是 $\gcd(x, y)$ 的倍数」1250. 检查「好数组」 则利用裴蜀定理判断「最大公约数是否为 1」可见「两个数的线性组合能被 $g$ 刻画」是这类数论题的共同底层逻辑。接收器编号与奇偶性对照表拿到 $m, n$ 之后只需看奇偶性即可定位接收器。原理在于奇数次反射会落在「对面」的墙上偶数次反射会回到「同侧」的墙上。$m$ 为奇数水平方向反射了奇数次最终停在东墙$x p$$m$ 为偶数水平方向反射了偶数次最终停在西墙$x 0$$n$ 为奇数垂直方向反射了奇数次最终停在北墙$y p$$n$ 为偶数垂直方向反射了偶数次最终停在南墙$y 0$。综合起来接收器位置与 $(m, n)$ 奇偶性的对应关系如下接收器角落坐标$m$ 奇偶性$n$ 奇偶性判定接收器 0东南角 $(p, 0)$奇数偶数m % 2 1 and n % 2 0接收器 1东北角 $(p, p)$奇数奇数m % 2 1 and n % 2 1接收器 2西北角 $(0, p)$偶数奇数其余情况$m$ 偶、$n$ 奇为什么不会出现 $m$、$n$ 同为偶数的情况因为 $m \frac{p}{g}$ 与 $n \frac{q}{g}$ 在约分后互质两个互质的整数不可能同为偶数否则仍有公因子 2。因此上述三个分支已经覆盖全部可能代码中的else分支可以放心地归结到接收器 2。这也解释了为什么题目描述中说「保证光线最终会遇到一个接收器」——西南角 $(0, 0)$ 对应 $m, n$ 同为偶数而这种情况被互质性排除了。算法步骤完整继承原文档给出的解题流程计算 $p$ 和 $q$ 的最大公约数 $g \gcd(p, q)$化简反射次数$m \frac{p}{g}$水平方向的反射次数$n \frac{q}{g}$垂直方向的反射次数根据 $m$ 和 $n$ 的奇偶性判断接收器编号都为奇数 → 返回 1东北角$m$ 为奇数、$n$ 为偶数 → 返回 0东南角其余情况$m$ 为偶数、$n$ 为奇数→ 返回 2西北角。代码实现标准解法直接使用 Python 标准库math.gcd完整代码与关键注释如下class Solution: def mirrorReflection(self, p: int, q: int) - int: from math import gcd # 第 1 步计算最大公约数 g gcd(p, q) # 第 2 步化简 m p // g # 水平方向的反射次数穿过竖线 x k * p 的次数 n q // g # 垂直方向的反射次数穿过横线 y k * p 的次数 # 第 3 步根据奇偶性判断接收器编号 if m % 2 1 and n % 2 1: return 1 # 东北角 (p, p) elif m % 2 1 and n % 2 0: return 0 # 东南角 (p, 0) else: # m % 2 0 and n % 2 1 return 2 # 西北角 (0, p)手写欧几里得算法版本如果不依赖标准库也可以像仓库中 0365. 水壶问题 的题解那样手写辗转相除法逻辑完全等价class Solution: def mirrorReflection(self, p: int, q: int) - int: def gcd(a: int, b: int) - int: 计算最大公约数欧几里得算法 / 辗转相除法 while b: a, b b, a % b return a g gcd(p, q) m, n p // g, q // g if m % 2 1 and n % 2 1: return 1 elif m % 2 1 and n % 2 0: return 0 return 2考虑到数据范围 $1 \le q \le p \le 10^{3}$无论是标准库还是手写版本计算量都极小无需任何额外的数据结构或状态记录。复杂度分析时间复杂度$O(\log \min(p, q))$即计算最大公约数欧几里得算法的时间复杂度空间复杂度$O(1)$只使用了常数个变量没有额外数据结构。相比之下若按直觉去模拟光线逐步反射步数将达到 $O(\frac{p}{g} \frac{q}{g})$并且需要记录方向与位置状态而数学解法把反射次数直接压缩进一次gcd调用是本题在效率与简洁性上的最优解。正确性验证折叠映射与手工走查展开平面的角落点 $(m \cdot p,\ n \cdot p)$ 折叠回原房间的坐标可由「翻折映射」给出对坐标 $x$若 $\lfloor x/p \rfloor$ 为偶数则取 $x \bmod p$为奇数则取 $p - (x \bmod p)$$y$ 同理。用该方法可以逐一验证上面的判定表$p$$q$$g$$m$$n$奇偶判定返回折叠验证2112偶1奇$m$ 偶、$n$ 奇2角落 $(4,2)$ → 折叠到 $(0,2)$即西北角接收器 23113奇1奇双奇1角落 $(9,3)$ → 折叠到 $(3,3)$即东北角接收器 14222偶1奇$m$ 偶、$n$ 奇2角落 $(8,4)$ → 折叠到 $(0,4)$即西北角接收器 26423奇2偶$m$ 奇、$n$ 偶0角落 $(18,12)$ → 折叠到 $(6,0)$即东南角接收器 05551奇1奇双奇1光线沿对角线直行最先命中东北角接收器 1特别地$p q$ 时 $g p$$m n 1$光线沿对角线一次性到达东北角对应接收器 1与直觉完全一致。这些用例均可作为提交前的自查样例。举一反三仓库中的 GCD / 贝祖定理家族本题是「几何直觉 数论化简」的典型结合。在《算法通关手册》中同一知识脉络还有多道题可以对照阅读0365. 水壶问题通过贝祖定理证明「可测量的水量必然是两壶容量最大公约数的倍数」与本题「首次命中角落对应最小整数解」共享同样的数论骨架1250. 检查「好数组」用裴蜀定理判断整组数的最大公约数是否为 1同样是「线性组合 $g$ 的倍数」思想1201. 丑数 III、0592. 分数加减运算、2427. 公因子的数目 等题也频繁使用gcd/ 最小公倍数进行约分与判定。若想系统梳理「几何 / 数学 / 数论」分类下的题目可参考分类总表 docs/00_preface/00_06_categories_list.md或从 docs/solutions/index.md 进入全书题解索引继续深入。小结镜面反射题的核心方法论可以概括为三句话遇反射先展开——把周期性镜面反射等价为无限平面上的直线传播让复杂的路径追踪退化为坐标几何问题用最小公倍数 / 最大公约数定位首个交点——$m \frac{p}{\gcd(p,q)}$、$n \frac{q}{\gcd(p,q)}$ 直接给出两个方向上的反射次数用奇偶性完成映射——奇数次反射落在对面墙、偶数次反射回到同侧墙由此只需三次分支判断即可返回接收器编号。掌握这一思路后凡涉及「矩形 / 房间内的镜面反弹、网格内的直线传播」类问题都可以先考虑展开模型再寻找数学上的最小周期解从而把模拟题改写为一行gcd的常数级判定。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐算法通关手册题解精讲LeetCode 0326「3 的幂」的数论判定法算法通关手册题解精讲LeetCode 0326「3 的幂」的数论判定法 导读 本文围绕《算法通关手册》AlgoNote中的 0326. 3 的幂 http教程文档知识库AlgoNote 算法通关手册LeetCode 0784 字母大小写全排列 —— 回溯与位运算双解法精讲AlgoNote 算法通关手册LeetCode 0784 字母大小写全排列 —— 回溯与位运算双解法精讲 本文围绕 LeetCode 0784「字母大小写全排教程文档知识库AlgoNote 算法通关手册LeetCode 0053 最大子数组和的动态规划与分治三解法精讲AlgoNote 算法通关手册LeetCode 0053 最大子数组和的动态规划与分治三解法精讲 导读 本文围绕「算法通关手册」AlgoNote 仓库中的经典教程文档知识库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
