本文涉及知识点

二进制求公约数

LeetCode2543. 判断一个点是否可以到达

给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。
每一步 ，你可以从点 (x, y) 移动到以下点之一：
(x, y - x)
(x - y, y)
(2 * x, y)
(x, 2 * y)
给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。
示例 1：
输入：targetX = 6, targetY = 9
输出：false
解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。
示例 2：
输入：targetX = 4, targetY = 7
输出：true
解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。
提示：
1 <= targetX, targetY <= 10⁹

预备知识

辗转相除法（欧几里得）求最大公约数

$$(a,b{)}_{\to }^{不失一般性，令a>=b}(c=a\mathrm{mod}b,d=b{)}_{\to }^{不失一般性，令c>=d}(e=c\mathrm{mod}d,f=d)\cdots$$
直到最后的两个数一个为0，则公约数是另外一个。比如：e为0，最大公约数就是f。f为0，最大公约数为e。
a,b不断变小，有限次数一定有一个数变为0。
令某两个数的最大公约数为q， $$则这两个数可以表示为q\times a,q\times b则q\times (a\mathrm{mod}b),q\times b的最大公约数为q$$
a%b 为0,也符合数学定义: 0和任何数x的最大公约数是x。

二进制求公约数

求a,b的最大公约数。
一，如果a，b都是偶数，则GCD(a,b) = 2*GCD(a,b)。
二，如果a 是偶数，b是奇数（反之类似）。GCD(a,b)=GCD(a/2,b)。b是奇数，所以他们的公约数不包括2。
三，两者都是奇数。
3.1，两者相等。a就是最大公约数。
3.2，a b不等，不失一般性，令a>b。GCD(a,b) == GCD(a+b,b) == GCD((a+b)/2,b)
由于a,b是不断变小，一定会相等。

数学

本题 $⟺$ (targetX, targetY)能否变成(1,1)。
如果 argetX, targetY 最大公约是g$\times$ 2^m ,按二进制求最大公约数的做法，最终变成(g,g)。如果g=1，则一定能到达。
下面来证明 g $\ne$ 1 ,则一定不能到达。
4种操作对公约数的影响只有两种：
一，最大公约数不变。
二，最大公约数除以2。
这4个操作若干次后，两个数的最大公约是：g$\times$ 2^m1 ,m1$\in$ [0,m]。
因为：g $\ne$ 1 ，故： g$\times$ 2^m1 $\ne$ 1 。

娱乐型求最大公约数

这种求公约数的方式不好理解，不要在工程中使用。

int GCD(int x, int y)
{
	if ((x && y))
	{
		while ((x %= y) && (y %= x));
	}
	return x + y;
}
class Solution {
public:
	bool isReachable(int targetX, int targetY) {
		const int g = GCD(targetX, targetY);
		return 0 == (g & (g - 1));
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

二进制求公约数

int GCD(int x, int y)
{	
	int ret = 1;
	while (x != y)
	{
		if (x < y)
		{
			swap(x, y);
		}
		const bool odd1 = x & 1;
		const bool odd2 = y & 1;
		if (odd1 & odd2)
		{
			x = (x + y) / 2;
		}
		else if (odd1)
		{
			y /= 2;
		}
		else if (odd2)
		{
			x /= 2;
		}
		else
		{
			ret *= 2;
			x /= 2;
			y /= 2;
		}
	}
	return x * ret;
}
class Solution {
public:
	bool isReachable(int targetX, int targetY) {
		const int g = GCD(targetX, targetY);
		return 0 == (g & (g - 1));
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。