【高级技巧】欧几里得：最大公约数的分组均衡应用

底层原理

求 a 与 b 的最大公约数：gcd(a, b) = gcd(b, a mod b)，辗转相除直到余数为 0，除数即答案——每次迭代规模至少砍半，复杂度 O(log min(a, b))。最小公倍数则由 gcd 推出：lcm = a 乘 b 除以 gcd。游戏里的落点：人数不等的队伍合并成整齐分组（求 gcd）、两个不同周期的刷新对齐（求 lcm）——商与余的数学是分组与调度的底层工具。

高级封装

辗转相除与公倍数。示例代码如下：

local function gcd(a, b)
    while b ~= 0 do
        a, b = b, a % b
    end
    return a
end
local function lcm(a, b)
    return a * b / gcd(a, b)
end
print(gcd(48, 36), lcm(48, 36))

输出 12 与 144——48 与 36 的最大公约 12，最小公倍 144。
联合阵型接线。示例代码如下：

local a, b = 48, 36
local g = gcd(a, b)
print("每组 " .. g .. " 人，甲队 " .. a / g .. " 组，乙队 " .. b / g .. " 组")

48 人与 36 人两队合并：每组 12 人、甲队 4 组乙队 3 组——参差的两队排出整齐阵型。掉落每 48 分钟刷新、资源每 36 分钟刷新，lcm 得 144：每 144 分钟两者重合，沙巴克资源点的世界事件就设在重合时刻。

性能对比

从 min(a,b) 向下枚举公约数最坏 O(min(a,b))：48 与 36 要试 12 次；欧几里得只辗转 2 次（48,36 到 36,12 到 12,0）。数字放大到百万级，枚举不可行而欧几里得仍是几十次迭代——数值越大，对数复杂度的优势越大。

适用边界

三个不适用场景：一是只需要判断两数是否互质（gcd 为 1），常规 gcd 已足够快，更快的随机化测试是多余；二是浮点输入——取余在浮点上有精度坑，先按倍率放大成整数再算；三是需要全部公约数列表的场景，gcd 只给最大值，枚举另走一遍。