Greatest Common Divisor
你会得到两个正整数 a 和 b。返回它们的最大公约数：能同时整除这两个数且没有余数的最大整数。
例如，能同时整除 8 和 12 的数有 1、2 和 4，所以答案是 4。
函数
- ainteger
- 第一个正整数
- binteger
- 第二个正整数
- 返回值integer
- 同时整除 a 和 b 的最大整数
约束条件
1 ≤ a ≤ 1091 ≤ b ≤ 109
示例
- 输入
- a = 12b = 18
- 输出
- 6
- 解释
12的约数是 1、2、3、4、6 和 12；18的约数是 1、2、3、6、9 和 18。两个列表中最大的约数是6。
- 输入
- a = 17b = 5
- 输出
- 1
- 解释
17和5都是质数，而且彼此不同，所以它们唯一的公约数是1。
- 输入
- a = 42b = 42
- 输出
- 42
- 解释
- 一个数可以整除自身，而且大于
42的数都不能整除42，所以42和42的最大公约数是42。
进阶
你能扩展欧几里得算法，使它还返回整数 x 和 y，满足 a × x + b × y = gcd(a, b) 吗？
提示
逐个打开提示，每个都会多透露一点。
a和b的公约数不可能大于两者中较小的那个数。对于两个接近10^9的数，你需要尝试多少个候选数？任何同时整除
a和b的数，也能整除a % b。因此，gcd(a, b)等于gcd(b, a % b)，而第二组数更小。持续将数对
(a, b)替换为(b, a % b)。当第二个数变为0时，第一个数就是答案。
题解
逐个尝试候选数在较小的数字上可行，但两个接近 10^9 且没有公因数的数字会让你尝试 10 亿次。欧几里得算法的规则 gcd(a, b) = gcd(b, a % b) 能让这对数字迅速缩小，因此不超过 10^9 的任何一对数字都不需要超过 43 步。
从较小的数字开始倒数
结果正确，但无法在最大的测试中运行完毕
思路
公因数不可能大于较小的那个数。将 d 设为 min(a, b)，然后每次减 1，直到它能同时整除这两个数。因为你是从最大的数开始往下找，所以第一个找到的就是最大公因数，而且循环最迟会在 1 时停止。对于 12 和 18，你会从 12 开始依次尝试到 7，并在 6 处停止。
每个候选数都要尝试一次。对于质数 999999937 和 999999929，答案是 1，所以循环几乎会运行 10^9 次。
算法
- 将
d设为a和b中较小的值。 - 当
a % d或b % d不为0时，将d减 1。 - 返回
d。
def gcd(a, b):
d = min(a, b)
while a % d != 0 or b % d != 0:
d -= 1
return d欧几里得算法
思路
将 a = q × b + r 写成 r = a % b。一个能整除 a 和 b 的数，也能整除 r = a - q × b；一个能整除 b 和 r 的数，也能整除 a = q × b + r。因此，(a, b) 和 (b, r) 有相同的公因数，最大的公因数也相同。
重复此过程，直到 b 为 0。任何数都能整除 0，所以 gcd(a, 0) = a。对于 12 和 18，数对依次变为 (12, 18)、(18, 12)、(12, 6)、(6, 0)，答案是 6。当 a 较小时，第一步会交换数对，所以你不需要排序。
每两步，较大的数至少减半，因此循环会运行 O(log(min(a, b))) 次。
算法
- 当
b不为0时，计算r = a % b。 - 将
a设为b，将b设为r。 - 当
b达到0时，返回a。
def gcd(a, b):
# gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
while b != 0:
a, b = b, a % b
return a
易错点和边界情况
- 按错误的顺序更新。先执行
a = b，再执行b = a % b，计算得到的是b % b，结果始终是0。先保存余数，或者一次性赋值。 - 循环结束时返回
b。此时b是0。 - 倒计时在
2时停止。这样一来，对于17和5这样的互质数对，就找不到答案。 - 重复相减，而不是使用余数。这样，计算
gcd(10^9, 1)需要减一亿次；一个%就能一次完成所有这些操作。
常见问题3
欧几里得算法的时间复杂度是多少？
需要 O(log(min(a, b))) 步，空间复杂度为 O(1)。最慢的输入是连续的斐波那契数：701408733 和 433494437 需要 42 步，较小的数在前时需要 43 步，这是任意一对不超过 10^9 的数中步数最多的情况。
最大公约数（GCD）和最小公倍数（LCM）有什么区别？
最大公约数是能同时整除两个输入值的最大数；最小公倍数是两个输入值都能整除的最小数。它们之间的关系是 gcd(a, b) × lcm(a, b) = a × b，因此最小公倍数是 a / gcd(a, b) × b。
两个互质数的最大公约数是多少？
这是 1：两个数互质，当且仅当它们没有共同的质因数。两个不同的质数总是互质的，两个连续整数也互质，例如 8 和 9。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def gcd(a, b):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
a = 12 b = 18
预期输出
6