藍橋杯真題解析：核桃數量問題（最小公倍數應用）

藍橋杯歷屆真題：核桃的數量

題目描述

小張帶領 3 個開發組加班，想給每組發一袋核桃，要求：

1. 三組核桃數量相同
2. 每組內部能平分（人數不同，不能打碎核桃）
3. 滿足條件的最小數量

輸入：三個正整數 a, b, c（< 30），分別為三組人數。
輸出：每袋核桃最少數量。

樣例

核心思路：求最小公倍數 (LCM)

每組人數為 a, b, c，核桃數需能被三者整除 → 求 LCM(a, b, c)。
數學公式：LCM(x, y) = x * y / GCD(x, y)，三數遞推：LCM(a, b, c) = LCM(LCM(a, b), c)。

Java 參考代碼（含 GCD 遞歸/輾轉相除法）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] a = new int[3];
        for (int i = 0; i < 3; i++) a[i] = in.nextInt();

        // 可選：排序優化（非必需）
        java.util.Arrays.sort(a);

        int lcm = lcm(a[0], a[1]);
        lcm = lcm(lcm, a[2]);
        System.out.println(lcm);
    }

    // 輾轉相除法求最大公約數
    private static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    // 最小公倍數
    private static int lcm(int x, int y) {
        return x / gcd(x, y) * y;  // 先除後乘防溢出
    }
}

複雜度分析

• 時間：O(log min(a,b)) — 輾轉相除法極快
• 空間：O(1)
• 數據範圍小（<30），甚至可暴力枚舉，但 LCM 做法更通用優雅

常見坑點提醒

• 整數溢出：x * y 可能超範圍，建議 x / gcd * y 先除後乘
• 輸入可能不按大小序，排序或不排序均不影響結果
• 注意題目要求「每袋數量」，非總數量

這道題考察基礎數論與代碼實現能力，掌握 GCD → LCM 模板，同類「最小公倍數」「齊次同步」問題（如燈光同步、行星對齊）皆可秒殺。