LeetCode 补充题 154. 最大公约数
题目描述
牛客原题： ✅ 补充题 154. 最大公约数
输入两个正整数
a、b，返回它们的最大公约数。
示例 1：
输入：
a = 8, b = 12
输出：4
解释： 4 是能够同时整除 8 和 12 的最大正整数。
提示：
-
a、b均为正整数。
题意分析
不必枚举两个数的所有约数，可以反复减去整倍数而保持公约数集合不变。除法取余一次就完成多次相减，使参与计算的数迅速减小。
解法：欧几里得算法保持公约数不变
核心思路
[!blue]
写成
a = q * b + r。任何同时整除a、b的数也整除r = a - q * b；反过来，任何同时整除b、r的数也整除a。因此gcd(a,b) = gcd(b,r)，每次替换保持答案不变。当
b != 0时计算r = a % b，再更新为(b,r)。余数满足0 <= r < b，后一个数严格缩小，最终必到 0；此时另一个数本身就是最大公约数。初始
a < b也无需特殊交换，第一次取余会自然将较大的数放到前面。Java 先保存余数避免覆盖旧值，Go 的同时赋值使用更新前的两个值。
解题步骤
- 在 b 非零时计算余数 r=a%b。
- 用 (b,r) 替代 (a,b)，继续消去整倍数部分。
- b 为零时返回 a。
代码实现
class Solution {
public int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
复杂度分析
- 时间复杂度：$O(\log \min (a,b))$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
a=qb+r，所以同时整除 a、b 等价于同时整除 b、r；每次替换都保持公约数集合不变。
易错点总结
[!yellow]
- 先保存 a%b，再更新 a、b，避免覆盖后算错余数。
- b 变为 0 时返回的是 a，不是返回 0；本题输入为正整数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1071. 字符串的最大公因子 | 简单 | 先验证两个字符串能由同一模式重复组成，再用长度的最大公约数确定公共模式长度。 |
| 365. 水壶问题 | 中等 | 容量组合的可达性由最大公约数约束，本题是该数论判断的基础工具。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！