NYOJ 972 核桃的數量：最小公倍數（LCM）處理空組

問題描述

三個開發組人數 a,b,c (0≤a,b,c<100)。核桃數需滿足：
1. 各組核桃數相同（前提是組有人）。
2. 組內能平分（整除人數）。
3. 滿足 1,2 的最小核桃數。
輸出該最小數。

分析

• 若某組人數為 0，該組不參與分配，不影響 LCM。
• 答案 = 所有非零人數的 LCM。
    若全部為 0？題目隱含至少一組有人，否則無意義。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c;
    while (cin >> a >> b >> c) {
        int ans = 1;
        bool first = true;
        for (int x : {a, b, c}) {
            if (x > 0) {
                if (first) { ans = x; first = false; }
                else ans = lcm(ans, x);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(log max(a,b,c)) 每測試用例，極快。
• 空間：O(1)。

關鍵點

• 0 不參與 LCM 計算（組無人則無需分配）。
• LCM 計算用 `a / gcd(a,b) * b` 避免中間溢出（此處數據小無憂）。
• 多組輸入直到 EOF。

簡單數論應用，注意 0 的特殊處理即可。