镜面反射（858）

这两天熟悉的朋友该知道我情绪不太好。但总不能借着由头，便拖期延稿诉衷肠。毕竟消除恐惧的最好方法就是面对恐惧。微笑着面对它，坚持才是胜利，加油！奥利给！

01、题目示例

王者荣耀新赛季出了个“镜”，那我也出个“镜”呗。那个不会玩，这个总该会“玩”吧？

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

示例：

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

上面的题目绕得很，大概就是这么个意思：

PNG

02、题目分析

这是一道数学题…不喜勿喷


我们知道光是由西南角发出的，也就是左下角。发出之后可能会出现多种情况（注意，下图略过了部分光线反射的情况）。看起来是十分复杂，无迹可寻。

PNG

但是如果我们把光线的运动轨迹拆开来看，就可以观测到，光线每经过一次折反，都会在纵向距离上移动 q（首次与东墙相距的距离）。同时，一旦其向上行走的距离为 p 的整数倍，就一定会碰到某个接收点（注意：这里我们不需要考虑北面墙是否存在，根据光的反射定律可得）可以参考一下下面这张图：

PNG

问题变得简单了，光线最终向上走的距离，其实就是 p 和 q 的最小公倍数。我们设最小公倍数为 L，会发现如果 L 是 p 的奇数倍，光线则到达北墙（可以参考上面的图）当 L 是 p 的 偶数倍，光线将会射到南墙。


问题来了，如果光线是射向南墙，因为只有一个接收器了，必定只能遇到接收器 0。但是如果射到了北墙，如何区分是 1 和 2。这回到了一个初中数学题，我们可以通过光线与东西墙的接触次数，来判断最终的落点是 1 还是 2。


根据分析，得出代码（这道题应该不需要给多语言版本吧，都长一样….）：

  1. //JAVA
  2. class Solution {    
  3.     public int mirrorReflection(int p, int q) {        
  4.         int m = p, n = q;        
  5.         int r;        
  6.         while (n > 0) {            
  7.             r = m % n;            
  8.             m = n;            
  9.             n = r;        
  10.         }        
  11.         if ((p / m) % 2 == 0) {            
  12.             return 2;        
  13.         } else if ((q / m) % 2 == 0) {
  14.             return 0;        
  15.         } else {            
  16.             return 1;       
  17.         }   
  18.     }
  19. }

执行结果：

PNG

这道题学会了吗？如果不会就不要玩镜了吧（皮一个）。


快来评论区留下你的想法吧！