Leetcode.858 镜面反射

题目链接

Leetcode.858 镜面反射 Rating ： 1881

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

• $1<=q<=p<=1000$

解法：数论

我们注意到光线每射出一次，水平距离移动 $p$，垂直距离移动$q$。

由于题目保证了，光线经过若干次射出之后，一定会遇到一个接收器。

假设光线共射出了 $k$ 次，那么光线在垂直方向移动的距离 $kq$ 一定是 $p$ 的倍数。因为这是一个边长为 $p$ 的正方形房间，接收器的位置从垂直方向上看都是 $p$ 的倍数。

因为 $kq$ 肯定是 $q$ 的倍数，这里同时也是 $p$ 的倍数，所以我们只需要让 $kq$ 为 $p$ 和 $q$ 的 最小公倍数 $lcm(p,q)$ 即可，$kq=lcm(p,q)$,$k=lcm(p,q)/q$。

我们可以通过 $k$ 的奇偶性来判断，光线的终点是左侧还是右侧。如果 $k$ 是奇数，那么说明光线是指向右侧的，即接收器只可能是 $0和1$；如果 $k$ 是偶数，那么说明光线是指向左侧的，即接收器只可能是 $2$。

我们可以通过 $n=lcm(p,q)/p$ 的奇偶性来判断，光线的终点是上方还是下方。如果 $n$ 是奇数，那么说明光线是上方的，即接收器只可能是 $2和1$；如果 $n$ 是偶数，那么说明光线是下方的，即接收器只可能是 $0$。

总结：

• 当 $n和k$ 同时为奇数时，光线的落点是在右上方，接收器只能是 $1$
• 当 $k$ 是奇数时，光的落点是在右侧，接收器是 $0$
• 当 $k$ 是偶数时，光的落点时在左侧，接收器是 $2$

时间复杂度： $O(log(max(p,q)))$

C++代码：

class Solution {
public:int mirrorReflection(int p, int q) {int lc = lcm(p,q);int k = lc / q , n = lc / p;k %=2 , n %= 2;if(k == 1 && n == 1) return 1;return k == 1 ? 0 : 2;}
};