【二进制求公约数】【数学】【数论】2543. 判断一个点是否可以到达

本文主要是介绍【二进制求公约数】【数学】【数论】2543. 判断一个点是否可以到达，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

二进制求公约数

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)^{不失一般性，令a >= b}_\rightarrow (c= a \mod b,d= b) ^{不失一般性，令c >= d}_\rightarrow (e=c \mod d,f=d) \cdots$
直到最后的两个数一个为0，则公约数是另外一个。比如：e为0，最大公约数就是f。f为0，最大公约数为e。
a,b不断变小，有限次数一定有一个数变为0。
令某两个数的最大公约数为q， $\times a,q \times b 则 q \times (a \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是不断变小，一定会相等。

数学

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛