NYOJ 核桃的數量——最小公倍數應用

題目描述

三組開發人員人數 a,b,c（可能為 0）。每組核桃數相同，且組內能平分。求最小總核桃數。

數學模型

• 設每組核桃數為 x，則總數 3x（三組都非零時）
• x 必須是該組人數的倍數 ⇒ x 是所有非零人數的公倍數
• 取最小公倍數 LCM
• 若某組人數為 0，該組不發核桃，總數相應減少

分情況公式

三組都非零：3 * LCM(a,b,c)
兩組非零：   2 * LCM(非零兩組)
一組非零：   該組人數
全零：       0

C++ 實現

#include <cstdio>
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() {
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)==3) {
        int ans=0;
        if(a&&b&&c) ans=3*lcm(a,lcm(b,c));
        else if(a&&b) ans=2*lcm(a,b);
        else if(a&&c) ans=2*lcm(a,c);
        else if(b&&c) ans=2*lcm(b,c);
        else if(a) ans=a;
        else if(b) ans=b;
        else if(c) ans=c;
        else ans=0;
        printf("%d\n", ans);
    }
    return 0;
}

樣例

輸入：2 4 5 → LCM=20 → 3×20=60
輸入：3 1 1 → LCM=3 → 3×3=9