本文涉及知识点
二进制求公约数
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 <= 109
预备知识
辗转相除法(欧几里得)求最大公约数
(
a
,
b
)
→
不失一般性,令
a
>
=
b
(
c
=
a
m
o
d
b
,
d
=
b
)
→
不失一般性,令
c
>
=
d
(
e
=
c
m
o
d
d
,
f
=
d
)
⋯
(a,b)^{不失一般性,令a >= b}_\rightarrow (c= a \mod b,d= b) ^{不失一般性,令c >= d}_\rightarrow (e=c \mod d,f=d) \cdots
(a,b)→不失一般性,令a>=b(c=amodb,d=b)→不失一般性,令c>=d(e=cmodd,f=d)⋯
直到最后的两个数一个为0,则公约数是另外一个。比如:e为0,最大公约数就是f。f为0,最大公约数为e。
a,b不断变小,有限次数一定有一个数变为0。
令某两个数的最大公约数为q,
则这两个数可以表示为
q
×
a
,
q
×
b
则
q
×
(
a
m
o
d
b
)
,
q
×
b
的最大公约数为
q
则这两个数可以表示为q \times a,q \times b 则 q \times (a \mod b) , q \times b 的最大公约数为q
则这两个数可以表示为q×a,q×b则q×(amodb),q×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是不断变小,一定会相等。
数学
本题
⟺
\iff
⟺ (targetX, targetY)能否变成(1,1)。
如果 argetX, targetY 最大公约是g
×
\times
× 2m ,按二进制求最大公约数的做法,最终变成(g,g)。如果g=1,则一定能到达。
下面来证明 g
≠
\neq
= 1 ,则一定不能到达。
4种操作对公约数的影响只有两种:
一,最大公约数不变。
二,最大公约数除以2。
这4个操作若干次后,两个数的最大公约是:g
×
\times
× 2m1 ,m1
∈
\in
∈ [0,m]。
因为:g
≠
\neq
= 1 ,故: g
×
\times
× 2m1
≠
\neq
= 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));
}
};
二进制求公约数
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));
}
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。