解题思路

题目要求把十六进制数转换成八进制数。十六进制最长 100000 位，不能先转成十进制（太大），要利用二进制作为中间桥梁。

核心规律：

• 十六进制的 1 位 = 二进制的 4 位（因为 16 = 2⁴）
• 八进制的 1 位 = 二进制的 3 位（因为 8 = 2³）

所以转换路线是：十六进制 → 二进制 → 八进制。

步骤：

1. 十六进制转二进制：每位十六进制数字（0~F）查表转成 4 位二进制，拼起来
2. 去前导 0：把开头多余的 0 去掉
3. 二进制转八进制：前面补 0 让长度是 3 的倍数，每 3 位一组转成 1 位八进制
4. 输出：把每组转出的八进制数字连起来

为什么要经过二进制？ 因为十六进制和八进制之间没有直接的简单对应，但都跟二进制有关（4 位和 3 位），转成二进制就统一了。

举例 十六进制 123ABC：

• 每位转 4 位二进制拼起来
• 再每 3 位一组转八进制，得到 4435274

参考代码

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

char num(string s) {  // 3 位二进制转 1 位八进制
    int r = 0, t = 1;
    for (int i = s.size() - 1; i >= 0; i--) {
        r += (s[i] - '0') * t;
        t *= 2;
    }
    return char(r + '0');
}

int main() {
    string t[16] = {"0000","0001","0010","0011","0100","0101","0110","0111",
                    "1000","1001","1010","1011","1100","1101","1110","1111"};
    string r, s, y;
    long long x;
    cin >> s;

    for (int i = 0; i < s.size(); i++) {  // 十六进制转二进制
        if (isdigit(s[i])) x = s[i] - '0';
        else x = s[i] - 'A' + 10;
        r += t[x];
    }

    while (r[0] == '0') r.erase(0, 1);  // 去前导 0

    if (r.size() % 3 == 1) r = "00" + r;
    else if (r.size() % 3 == 2) r = "0" + r;

    for (int i = 0; i < r.size(); i += 3) {  // 每 3 位转八进制
        y = r.substr(i, 3);
        cout << num(y);
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，N 为十六进制位数
• 空间复杂度：O(N)，存二进制字符串