参考答案及解析

题目1：基础GCD计算

判断题

1. √ 欧几里得算法基于这个原理
2. √ 两个不同的素数互质，最大公约数为1
3. √ 如果a能被b整除，那么gcd(a, b) = b

选择题 4. C gcd(56, 98) = gcd(98, 56) = gcd(56, 42) = gcd(42, 14) = 14 5. B 欧几里得算法的时间复杂度是O(log min(a, b))

题目2：基础LCM计算

判断题

1. √ 这是计算最小公倍数的标准公式
2. √ 最小公倍数至少是a和b中较大的那个
3. √ 互质的两个数，最小公倍数就是它们的乘积

选择题 4. C lcm(15, 20) = 15×20 / gcd(15, 20) = 300 / 5 = 60 5. C 两种写法都可以避免溢出，先除后乘

题目3：多个数的GCD和LCM

判断题

1. √ 多个数的GCD可以通过迭代两两计算得到
2. √ 多个数的LCM也可以通过迭代两两计算得到
3. √ 最大公约数不会超过最小公倍数

选择题 4. C gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6 5. B lcm(4, 6, 8) = lcm(lcm(4, 6), 8) = lcm(12, 8) = 24

题目4：GCD应用-分数化简

判断题

1. √ 分数相加需要先通分
2. √ 分数相乘直接分子乘分子，分母乘分母
3. √ 化简分数需要找到分子分母的最大公约数

选择题 4. D 1/2 + 1/3 = 3/6 + 2/6 = 5/6 5. B 2/3 × 3/4 = 6/12 = 1/2

题目5：GCD与数论结合-线性同余方程

判断题

1. √ 扩展欧几里得算法可以求解贝祖等式
2. √ 这是线性同余方程有解的充要条件
3. √ 如果有一个解x₀，那么x₀ + k×(m/d)都是解，其中d = gcd(a, m)

选择题 4. D 3×4 = 12 ≡ 2 (mod 5)，所以x ≡ 4 (mod 5) 5. B gcd(4, 6) = 2，2能整除2，所以有解。解为x ≡ 2 (mod 3)和x ≡ 5 (mod 6)

专题总结

最大公因数（GCD）和最小公倍数（LCM）是数论中的基础概念，在算法竞赛和编程中有广泛应用。

关键知识点：

1. 欧几里得算法：

   • 递归实现：gcd(a, b) = gcd(b, a mod b)
   • 迭代实现：while循环直到b=0
   • 时间复杂度：O(log min(a, b))

2. 最小公倍数计算：

   • lcm(a, b) = a × b / gcd(a, b)
   • 注意避免整数溢出：先除后乘

3. 扩展应用：

   • 分数运算：通分、约分
   • 线性同余方程：ax ≡ b (mod m)
   • 多个数的GCD和LCM：迭代计算

4. 相关性质：

   • 如果gcd(a, b) = 1，则a和b互质
   • gcd(a, b) × lcm(a, b) = a × b
   • 对于多个数，GCD和LCM满足结合律