（本文内容由AI生成，请审慎阅读）
作用：求两个正整数的最大公约数（GCD，最大公因数）
最大公约数：能同时整除 a 和 b 的最大整数，记作 \(\gcd(a,b)\)
核心定理（辗转相除）：
\(\boldsymbol{\gcd(a,b) = \gcd(b,\ a \bmod b)}\) 一直重复，直到余数为 0，此时的 b 就是答案。
前提：\(a>b>0\)；\(a \bmod b\) 就是 a 除以 b 的余数
举个例子：求 gcd (48, 18)
- \(\gcd(48,18) \Rightarrow 48 \bmod 18 = 12\) → \(\gcd(18,12)\)
- \(\gcd(18,12) \Rightarrow 18 \bmod 12 = 6\) → \(\gcd(12,6)\)
- \(\gcd(12,6) \Rightarrow 12 \bmod 6 = 0\) → 余数是 0，停止 ✅ 答案：\(\boldsymbol{6}\)
Python 递归写法（竞赛常用）
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
print(gcd(48, 18))
Python 迭代写法（不容易爆栈，推荐竞赛）
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
内置快捷方式（Python3.5+）
import math
print(math.gcd(48,18))
⚠️ 注意：math.gcd 只返回非负数，而且默认忽略负数；另外它返回的是两个数绝对值的 gcd，而且 math.gcd (a,b) 要求 b 不能为 0；还有一个坑：math.gcd 只支持两个数。
扩展：扩展欧几里得算法（ExGCD）
欧几里得只能求最大公约数； 扩展欧几里得可以同时求出一组整数 \(x,y\)，满足：
\(ax + by = \gcd(a,b)\) 信奥里用来解不定方程、求模逆元，是数论高频考点。
配套知识点（竞赛常一起考）
- 最小公倍数：\(\boldsymbol{\text{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}}\)
def lcm(a,b):
return a * b // gcd(a,b)
评论