Mirror Reflection

858. Mirror Reflection

class Solution {
int gcd(int a,int b)
{
    while(true) {
        int r = a%b;
        if (r == 0) {
            return b;
        }
        a = b;
        b = r;
    }
}

public:
    int mirrorReflection(int p, int q) {
        int lcm = p * q / gcd(p, q);
        int result = 2, pp = lcm / q, qq = lcm / p;
        if (pp % 2) {
            --result;
        }
        if (qq % 2 == 0) {
            --result;
        }
        return result;
    }
};

한 상자 내에서 반사 된다고 생각하면 너무 어렵고, 사각형의 오른쪽과 위로 확장해서 레이저가 확장된 사각형의 꼭지점에 닿는 점을 구하면 쉽다.
p 와 q 는 정수비를 가지게 되므로 p, q 의 최소공배수를 구해서 p, q 로 나누면 레이저가 꼭지점으로 닿는 큰 삼각형을 그리고 정수비 pp, qq 를 구한다.

확장된 사각형의 각 꼭지점 후보는 1층에서 1,2,1,2 가 반복, 2층에서 0,1,0,1 이 반복…
답을 2로 가정하고 가로, 세로 값을 계산하면,
pp 개수가 2로 나뉘어 떨어지지 않으면, x축 1인 컬럼, qq 개수가 2로 나눠떨어지면 y축 0인 컬럼이므로 각각 1씩 빼주면 최종닿는 점을 구할 수 있다.

Time: O(log(p, q))

• 최대공약수 구하는 시간 log(n), 나머지 계산은 O(1)

Space: O(1)