本文涉及的知识点

数论：质数、最大公约数、菲蜀定理

LeetCode858. 镜面反射

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。
正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。
返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。
示例 1：

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

模拟

折射有两个方向，一个在屋内，一个在屋外，忽略屋外，保留屋内。

最小公倍数

水平光竖直光都是运行p距离后更换方向。
光到达4个顶点时，水平光和竖直光都运行了p的整数倍。
令水平的光的速度为p，则竖直光的速度为q。假定运行了t单位时间则t是整数，即qt也是p的整数倍。$\to$ qt和p,q的公倍数。只需要计算最小公倍数。因为：a，如果首先经过出起点外的顶点，则结束。b，如果首先经过起点，则因为无限循环而无解。与本体有解矛盾。
t= lcm(p,q)/q。
水平光运行了,t周期。如果t时奇数，则是0或1，否则是2。
竖直光运行了tq/p周期，如果是奇数，则是1,2，否则是0。
cycle：周期

代码

核心代码

	class Solution {
		public:
			int mirrorReflection(int p, int q) {
				const int qt = lcm(p, q);
				const int hCycle = qt / q;
				const int vCycle = qt / p;
				if (hCycle & 1) {
					if (vCycle & 1) { return 1; }
					return 0;
				}
				return 2;
			}
		};

单元测试

		TEST_METHOD(TestMethod11)
		{
			auto res = Solution().mirrorReflection(2, 1);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().mirrorReflection(3, 1);
			AssertEx(1, res);
		}