Those of you who know me well these days should know that I’m not in a good mood. But can not always by the head, they delayed the draft to tell the truth. After all, the best way to eliminate fear is to face it. Face it with a smile, persistence is victory, come on! Ollie give!

01. Examples of topics

The new season of King of Glory has a “mirror”, so I have a “mirror”. That one can’t play. Surely this one can play?

Problem 858: Specular reflection
There was a special square room with a mirror on each wall. Each corner except the southwest corner has a receiver, numbered 0,1, and 2. The wall of the square room is p in length. A laser beam is emitted from the southwest corner and will first meet the east wall. The distance from the incident point to receiver 0 is Q. Returns the number of receivers that the ray first encounters (ensuring that the ray eventually encounters a receiver).

Example:

Input: p = 2, q = 1Output: 2Explanation: This ray meets receiver 2 the first time it is reflected back to the wall on the left.Copy the code

The above topic is very round, which is roughly the meaning of:


02. Topic analysis

It’s a math problem… Don’t like do not spray


We know that light is coming from the southwest corner, the lower left corner. There are many things that can happen after it’s emitted (note that the image below skips some of the reflection). It looks so complicated, there’s no trace.


But if we break down the path of the light, we can observe that the light travels by q in the longitudinal distance (the first distance from the east wall) every time it is inverted. At the same time, once it has traveled an integer multiple of P, it is bound to hit some receiving point (note: we do not need to consider the existence of the north wall here, according to the law of light reflection). Take a look at the following diagram:


So the problem becomes simple, the distance that the light ray ends up traveling up, is actually the least common multiple of p and q. If L is an odd multiple of P, the light will go to the north wall. If L is an even multiple of P, the light will go to the south wall.


The problem is, if the light is going to the south wall, because there’s only one receiver left, it must only hit receiver zero. But if it hits the north wall, how do you tell the difference between a 1 and a 2. This time comes to a math problem in junior high school. We can judge whether the final falling point is 1 or 2 by the number of times the light touches the east and west walls.


According to the analysis, the code (this problem should not need to give the multi-language version, are long the same….) :

//JAVA
class Solution {    
    public int mirrorReflection(int p, int q) {        
        int m = p, n = q;        
        int r;        
 while (n > 0) {  r = m % n;  m = n;  n = r;  }  if ((p / m) % 2= =0) {  return 2;  } else if ((q / m) % 2= =0) {  return 0;  } else {  return 1;  }  } } Copy the code

Execution Result:


Have you learned the problem yet? Don’t play with mirrors if you can’t.


Leave your thoughts in the comments section!

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download