【二进制求公约数】【数学】【数论】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 ( 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× 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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。