README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/0800-0899/0858.Mirror%20Reflection/README.md	几何 数学 数论

858. 镜面反射

English Version

题目描述

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= q <= p <= 1000

解法

方法一：数学

根据题意，光线在每次反射时，都会向上或向下移动 $q$ 的距离，向右移动 $p$ 的距离。而由于光线最后一定会遇到接收器，因此，我们需要找到一个最小的 $k$，使得 $k \times q$ 是 $p$ 的倍数。

同时，根据 $k$ 的奇偶性，我们可以确定光线最终到达了西侧还是东侧。如果 $k$ 是偶数，那么光线最终到达的是西侧，否则光线最终到达的是东侧。

另外，根据 $k \times q$ 除以 $p$ 的结果的奇偶性，我们可以确定光线最终到达的是北侧还是南侧。如果 $k \times q$ 是 $p$ 的偶数倍，那么光线最终到达的是南侧，否则光线最终到达的是北侧。

时间复杂度 $O(\log p)$，空间复杂度 $O(1)$。

Python3

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        g = gcd(p, q)
        p = (p // g) % 2
        q = (q // g) % 2
        if p == 1 and q == 1:
            return 1
        return 0 if p == 1 else 2

Java

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

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

C++

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

Go

func mirrorReflection(p int, q int) int {
	g := gcd(p, q)
	p = (p / g) % 2
	q = (q / g) % 2
	if p == 1 && q == 1 {
		return 1
	}
	if p == 1 {
		return 0
	}
	return 2
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

TypeScript

function mirrorReflection(p: number, q: number): number {
    const g = gcd(p, q);
    p = Math.floor(p / g) % 2;
    q = Math.floor(q / g) % 2;
    if (p === 1 && q === 1) {
        return 1;
    }
    return p === 1 ? 0 : 2;
}

function gcd(a: number, b: number): number {
    return b === 0 ? a : gcd(b, a % b);
}