進制轉換 題解

簡潔題意

給一個 \(A\) 進制表示的非負整數 \(x\)（\(2 \le A, B \le 36\)，位數字 \(10 \sim 35\) 用大寫 A ~ Z），把它轉成 \(B\) 進制輸出。保證 \(x\) 的十進制值不超過 \(10^{18}\)。

解法

這題就是把第十五單元的兩個方向接起來：先把 \(A\) 進制字串變成整數（15.3），再把整數變成 \(B\) 進制字串（15.4）。十進制只是中繼站，程式裡就是一個 long long。

第一步用 15.3 的累積式，從最高位往下掃：

\[\texttt{val} = \texttt{val} \times A + \texttt{digit}\]

字元轉數值是 8.2 的活：數字 c - '0'、字母 c - 'A' + 10。

第二步用 15.4 的「取個位、去個位」：反覆取 val % B、再 val /= B，取出的位由低到高，最後 reverse 翻回來（或倒著印）。數值轉字元同樣照 8.2：'0' + d、\(10\) 以上 'A' + (d - 10)。

兩個 15.4 講過的坑這題都在：\(x = 0\) 要特判（剝位迴圈一次都不會跑，什麼都印不出來），以及 val 要用 long long——值上看 \(10^{18}\)，int 一路乘上去必溢位（上冊 2.9）。

拿範例 1 走一遍：36（十進制）讀進來是 \(36\)；轉 \(36\) 進制取 \(36 \bmod 36 = 0\)、剩 \(1\)，再取 \(1\)——由低到高是 0、1，翻回來就是 10。

常犯錯誤

  • val 開 int（WA）：範例 3 的值就是 \(10^{18}\)，讀到一半就溢位
  • \(x = 0\) 沒特判（WA）：印出空字串
  • 忘了翻轉（WA）：剝位取出的順序是低位在前，範例 1 會印成 01
  • 字母對映錯（WA）：A 是 \(10\) 不是 \(11\)；範例 2 的 Z 是 \(35\)

參考程式碼

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 進制位字元 <-> 數值（8.2）
int charToDigit(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    return c - 'A' + 10;
}
char digitToChar(int d) {
    if (d < 10) return '0' + d;
    return 'A' + (d - 10);
}

int main() {
    int A, B;
    string s;
    cin >> A >> B >> s;

    long long val = 0;                       // 值上看 10^18：用 long long
    for (int i = 0; i < (int)s.size(); i++) {
        val = val * A + charToDigit(s[i]);   // 15.3：舊值整體升一位，個位放新數字
    }

    if (val == 0) {                          // 15.4 的特判：0 在任何進制都是 "0"
        cout << 0 << '\n';
        return 0;
    }
    string ans;
    while (val > 0) {                        // 15.4：取個位、去個位
        ans += digitToChar(val % B);
        val /= B;
    }
    reverse(ans.begin(), ans.end());         // 取出順序是低位在前，翻回來
    cout << ans << '\n';
    return 0;
}

複雜度：\(O(|x| + \text{輸出位數})\)。