从“虫群”到“真分数”：用Java搞定蓝桥杯里的GCD/LCM实战题（附完整代码）

在算法竞赛的战场上，数论问题往往是最考验选手基本功的试金石。蓝桥杯等赛事中，最大公约数（GCD）和最小公倍数（LCM）相关题目出现频率居高不下，从“抗击虫群”的药物配比到“最简真分数”的序列生成，这些看似迥异的题目背后都藏着相同的数学内核。本文将带您穿透题目表象，直击算法本质，用Java代码实现从问题识别到AC通过的完整闭环。

1. GCD/LCM核心算法精讲

1.1 欧几里得算法的现代演绎

辗转相除法之所以历经2300年仍被广泛应用，源于其惊人的简洁性与效率。其时间复杂度为O(log min(a,b))，这意味着即使处理百万级数字，递归深度也不会超过20层。

// 经典递归实现
public static int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a;
}

// 迭代版本（避免栈溢出风险）
public static int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

注意：当处理极大整数时，迭代版本更具稳定性。Java的BigInteger类内置gcd实现，适合竞赛中的高精度需求。

1.2 LCM的优化计算技巧

最小公倍数与最大公约数的关系可表示为：

lcm(a,b) = |a*b| / gcd(a,b)

但直接计算a*b可能导致整数溢出，因此推荐先除后乘：

public static int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 调整运算顺序防止溢出
}

典型应用场景对比 ：

场景特征	适用算法	示例题目
需要均分或最大分组	GCD	抗击虫群、分糖果
涉及周期同步或重复出现	LCM	行星相遇、信号同步

2. 题目逆向拆解方法论

2.1 识别GCD/LCM特征的黄金法则

当题目出现以下关键词时，应立即考虑GCD/LCM解法：

• "最大公约"、"最少分割" → GCD
• "最小公倍"、"最早同时" → LCM
• "最简分数"、"互质判断" → gcd(a,b)==1

实战案例分析：抗击虫群

题目要求用固定量p的药物注满n和m的容器，实际上等价于求n和m的最大公约数。因为：

• 每次操作增加p单位药量
• 最终n和m都必须是p的整数倍
• 要操作次数最少，需p尽可能大

// 抗击虫群AC代码核心段
int p = gcd(Math.max(n, m), Math.min(n, m));
System.out.println(p);

2.2 边界条件处理指南

竞赛题目常见的陷阱包括：

• 零值处理（gcd(a,0) = a）
• 负数处理（gcd(-15, -18) = 3）
• 大数运算（超过int范围）

// 带边界检查的增强版GCD
public static int safeGcd(int a, int b) {
    if (a == Integer.MIN_VALUE || b == Integer.MIN_VALUE)
        throw new ArithmeticException("Overflow risk");
    a = Math.abs(a);
    b = Math.abs(b);
    if (a == 0) return b;
    if (b == 0) return a;
    return gcd(b, a % b);
}

3. 竞赛真题深度剖析

3.1 最简真分数序列生成（蓝桥杯1123题）

题目要求列出分母为40的所有最简真分数，本质是筛选与40互质的分子。关键点在于：

• 遍历1到39的分子
• 检查gcd(分子,40)==1
• 格式化输出带逗号分隔

// 优化后的输出处理
StringBuilder sb = new StringBuilder();
for (int i = 1; i < 40; i++) {
    if (gcd(i, 40) == 1) {
        sb.append(i).append("/40,");
    }
}
System.out.print(sb.toString());

性能优化技巧 ：

1. 预先计算40的质因数：2,5
2. 只需检查分子不被2或5整除
3. 使用StringBuilder减少IO开销

3.2 最大公约数与最小公倍数组合题（1011题）

这类基础题目考察的是GCD与LCM的联合应用。注意输出格式要求：

// 输入处理优化方案
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
System.out.printf("%d %d", gcd(a,b), lcm(a,b));

提示：使用printf可以避免字符串拼接，在频繁输出时提升约15%性能

4. 高阶应用与调试技巧

4.1 多数字的GCD/LCM扩展

竞赛中可能遇到多个数字的情况，此时需要链式计算：

// 数组版GCD计算
public static int multiGcd(int[] numbers) {
    int result = numbers[0];
    for (int i = 1; i < numbers.length; i++) {
        result = gcd(result, numbers[i]);
        if(result == 1) break; // 提前终止优化
    }
    return result;
}

4.2 调试与测试用例设计

推荐自测用例组合：

测试用例	预期结果	测试目的
gcd(0, 5)	5	零值处理
gcd(-15, -18)	3	负数处理
lcm(21, 6)	42	常规LCM验证
gcd(1<<30, (1<<30)-1)	1	大数边界检查

// JUnit测试示例
@Test
public void testGcdEdgeCases() {
    assertEquals(5, gcd(0, 5));
    assertEquals(3, gcd(-15, -18));
    assertEquals(1, gcd((1<<30), (1<<30)-1));
}

4.3 常见WA原因分析

根据竞赛统计，GCD/LCM题目的错误主要集中在：

1. 忽略交换律：gcd(a,b)结果与参数顺序无关，但某些实现可能受影响
2. 整数溢出：特别是计算lcm时a*b的操作
3. 输入处理：未正确处理多组测试数据的情况
4. 输出格式：漏写分隔符或空格

// 安全输入处理模板
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {  // 处理多组case
    int a = sc.nextInt();
    int b = sc.nextInt();
    // ...计算逻辑
}