[LeetCode]Mirror Reflection

这道题我们需要巧妙的想法，如果我们根据p和q把整个屋子关于x或者y轴镜像，我们不难找到其中的规律，如下图所示：

从上图可以看到，规律如下，如果我们把p和q约成最简分数(6/4->3/2)：

• 关于y轴对称偶数次，x轴对称奇数次，我们会到达2
• 关于y轴对称奇数次，x轴对称偶数次，我们会到达0
• 关于y轴对称奇数次，x轴对称奇数次，我们会到达1
• 关于y轴对称偶数次，x轴对称偶数次，不可能，因为这代表可以继续约分

所以我们求gcd(p, q)即可，时间复杂度O(log(p + q))，代码如下：

	class Solution{
	public:
	int mirrorReflection(int p, int q) {
	int divisor = gcd(p, q);
	p /= divisor;
	q /= divisor;
	int ans = 1;
	if (p % 2 == 0)ans = 2;
	if (q % 2 == 0)ans = 0;
	return ans;
	}
	private:
	int gcd(int a, int b)
	{
	if (a < b)return gcd(b, a);
	if (!b)return a;
	return gcd(b, a % b);
	}
	};

view raw Mirror Reflection.cpp hosted with ❤ by GitHub