ACM 進制轉換問題詳解：從基礎到高精度

問題背景

進制轉換是計算機科學基礎，ACM 競賽中常見變體：大整數進制轉換、負進制、非標準進制（如斐波那契進制）、帶小數點轉換等。NJUPT OJ 1012 為典型大整數任意進制互轉題目。

核心算法

1. 標準除基取餘法（十進制 → 任意進制）

string toBase(long long n, int base) {
    if (n == 0) return "0";
    string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string res;
    bool neg = n < 0;
    if (neg) n = -n;
    while (n) {
        res.push_back(digits[n % base]);
        n /= base;
    }
    if (neg) res.push_back('-');
    reverse(res.begin(), res.end());
    return res;
}

2. 霍納法則（任意進制 → 十進制）

long long fromBase(const string &s, int base) {
    long long res = 0;
    for (char c : s) {
        int val = isdigit(c) ? c - '0' : toupper(c) - 'A' + 10;
        res = res * base + val;
    }
    return res;
}

3. 大整數進制轉換（高精度）

當數字超出 64 位範圍，需用數組/字符串模擬除法與乘法：

• 輸入為字符串，逐位處理。
• 除基取餘：模擬手算長除法，商存新數組，餘為當前位。
• 乘基加位：從高位到低位，res = res * base + digit，用高精度乘法/加法。

// 大整數除以小整數，返回商(字符串)和餘數
pair divmod(const string &num, int base) {
    string quot;
    int rem = 0;
    for (char c : num) {
        int cur = rem * 10 + (c - '0');
        quot.push_back('0' + cur / base);
        rem = cur % base;
    }
    // 去除前導零
    size_t pos = quot.find_first_not_of('0');
    if (pos == string::npos) quot = "0";
    else quot = quot.substr(pos);
    return {quot, rem};
}

進階變體

負進制轉換

如基數 -2：餘數必須非負，若餘數 < 0，則 rem += abs(base); quot++。

非標準進制（如斐波那契進制）

利用貪心：從最大斐波那契數開始減，對應位置 1，不連續放 1（Zeckendorf 定理）。

帶小數部分轉換

• 整數部分：除基取餘。
• 小數部分：乘基取整，重複直到小數為 0 或達到精度限制。注意循環小數截斷。

常見坑點

• 輸入為 0 直接返回 "0"。
• 基數範圍檢查（通常 2~36）。
• 大小寫統一：輸出大寫，輸入不區分大小寫。
• 負數處理：記錄符號，轉正處理，最後加符號。
• 高精度除法中商的前導零去除。

模板總結

string convertBase(string num, int fromBase, int toBase) {
    // 1. fromBase -> 十進制 (大整數)
    // 2. 十進制 -> toBase (大整數)
    // 合併優化：直接在 fromBase 和 toBase 之間轉換，避免中間十進制大數
}

競賽中建議預寫高精度加減乘除模塊，組合出通用進制轉換工具。