C# 最小公倍數（LCM）演算法：基於 GCD 的高效實作

數學關係

最小公倍數：LCM(a,b) = |a×b| / GCD(a,b)。例：12 與 9，GCD=3，LCM=12×9/3=36。

核心實作

public long Lcm(long a, long b)
{
    a = Math.Abs(a); b = Math.Abs(b);
    long g = Gcd(a, b);
    return a / g * b; // 先除後乘，降低溢位風險
}

private int Gcd(int a, int b)
{
    while (b != 0) { int r = a % b; a = b; b = r; }
    return a;
}

多數 LCM：遞歸/迭代歸約

原文件採用配對歸約（兩兩合併），支援奇數個參數：

public int GetLcm(params int[] nums)
{
    if (nums.Length == 1) return nums[0];
    var list = new List();
    for (int i = 0; i < nums.Length - 1; i += 2)
        list.Add(Lcm(nums[i], nums[i + 1]));
    if (nums.Length % 2 == 1) list.Add(nums[^1]);
    return GetLcm(list.ToArray()); // 遞歸歸約
}

// 迭代版更簡潔
public int LcmMultiple(params int[] nums)
{
    int l = nums[0];
    for (int i = 1; i < nums.Length; i++)
        l = Lcm(l, nums[i]);
    return l;
}

溢位處理策略

• int 範圍有限（±21 億），a*b 極易溢位。
• 改用 long（±9×10¹⁸）或 BigInteger（任意大小）。
• 先除後乘：a / g * b 保證中間結果 ≤ max(a,b)。

應用場景

• 分數加減通分、週期性事件同步（如多任務排程）、齒輪傳動比計算、密碼學（RSA 模數相關）。