GCD / LCM 最大公约数 / 最小公倍数
基础概念
基通俗讲解
GCD（最大公约数）是能同时整除两数的最大正整数；LCM（最小公倍数）是两数公共倍数里最小的。二者关系：a×b = gcd×lcm。
核心必背考点
背直接默写拿分
- 辗转相除：
gcd(a,b)=gcd(b,a%b)，b=0 时 gcd=a。 lcm(a,b)=a/gcd(a,b)*b（先除后乘防溢出）。- gcd(a,0)=a；gcd(a,a)=a。
高频难点 / 拉分考点
难考场极易丢分
算 lcm 写成 a*b/gcd 可能溢出（a*b 超大）。规范：a/gcd*b 先除后乘。
出题陷阱
坑文字套路
- gcd(0, x) = x，别误以为 0。
- 多个数的 gcd/lcm 可两两合并。
90分高分技巧
技速算捷径
小数字直接分解质因数取最小/最大幂次得 gcd/lcm；大数字用辗转相除，手算几步即出。
梯度真题
基础gcd(48,36)
48%36=12，36%12=0 → 12。
| 1 | int gcd(int a,int b){ return b?gcd(b,a%b):a; } |
| 2 | gcd(48,36); |
▍解析：答案 12。
中档lcm(12,18)
gcd=6，lcm=12/6*18=36。
▍解析：答案 36。
压轴lcm 防溢出写法
先除后乘。
| 1 | long long lcm(long long a,long long b){ |
| 2 | return a/gcd(a,b)*b; // 先除再乘 |
| 3 | } |
▍解析：避免 a*b 溢出。
记忆口诀
技📌 记忆口诀
“辗转相除取余尽，b为零时a是根；公倍先除后乘好，乘除交换不溢损。”
📝 本节自测共 6 题
做完点「提交本节自测」即时判分；单选 / 多选 / 填空混合，答错可一键收入错题本。
gcd(12, 18) 等于？
✅ 正确答案：A
12 与 18 最大公约数为 6。
lcm(4, 6) 等于？
✅ 正确答案：A
4×6 / gcd(4,6)=24/2 = 12。
gcd(a,b) = gcd(b, a mod b) 是哪种算法？
✅ 正确答案：A
这是欧几里得（辗转相除）算法。
下列属于组合数学常用结论的有？（多选） 多选题 中
✅ 正确答案：ABC
排列 / 组合 / 错排都是经典计数工具；质数没有简单精确公式。
2 的 10 次方等于 ____ 。（填空） 填空题 易
✅ 正确答案：1024
2^10 = 1024，常用作 1K。
用扩展欧几里得求 gcd(30, 12) = ____ 。（填空） 填空题 难
✅ 正确答案：6
30 与 12 的最大公约数是 6。