NYOJ 最強 DE 戰斗力：大數乘法與最優分組策略

問題大意

將 N (≤1000) 名士兵分成若干隊伍，戰斗力為各隊人數乘積。求最大戰斗力並輸出完整結果（大數）。

數學規律

將 N 拆分為若干正整數之和，使乘積最大。最優策略：
盡量拆成 3，餘數處理：
- N % 3 == 0：全 3
- N % 3 == 1：拆兩個 2，其餘 3 (因 3+1 < 2+2)
- N % 3 == 2：拆一個 2，其餘 3

大數乘法實現

用數組模擬十進制乘法，低位在前：

int a[205] = {1}; // 存儲結果，a[0] 為個位
void multiply(int x) {
    int carry = 0;
    for (int i = 0; i < 200; ++i) {
        carry += a[i] * x;
        a[i] = carry % 10;
        carry /= 10;
    }
}

完整代碼

#include <bits/stdc++.h>
using namespace std;
int ans[205];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        fill(ans, ans+205, 0); ans[0] = 1;
        int n3 = N / 3;
        if (N % 3 == 1) n3--; // 餘 1 時減一個 3，補兩個 2
        for (int i = 0; i < n3; ++i) multiply(3);
        if (N % 3 == 1) { multiply(2); multiply(2); }
        else if (N % 3 == 2) multiply(2);
        // 輸出大數（高位在前）
        int i = 204;
        while (i > 0 && ans[i] == 0) --i;
        for (; i >= 0; --i) printf("%d", ans[i]);
        puts("");
    }
    return 0;
}

示例驗證

N=5：5%3=2 → 3×2=6 ✓
N=6：全 3 → 3×3=9 ✓
N=7：7%3=1 → 3×2×2=12 ✓

關鍵點

1. 數學證明：對實數，e 為最優底數；整數情況下 3 最優
2. 大數乘法數組長度 205 足夠容納 3³³³ ≈ 10¹⁵⁹
3. 輸出時跳過前導零，至少輸出一位

此題結合了數學規律發現與大數運算實現，是 ACM 入門級經典綜合題。