解题思路

题目要求把一个十进制数转换成八进制。n 最大到 10^12，超出 int 范围，要用 long long。

方法：除 8 取余，倒序排列。

十进制转八进制，就是用这个数不断除以 8，记下每次的余数，最后把余数从下往上（反过来）写出来。

步骤：

1. 用 n 除以 8，得到余数（0~7），这是八进制的最后一位
2. n 变成 n÷8
3. 重复，直到 n 变成 0
4. 把记录下来的余数倒序拼起来就是八进制结果

举个例子 100000 转八进制：

• 100000÷8=12500 余 0
• 12500÷8=1562 余 4
• ……
• 最后倒序得到 303240

为什么要倒序？ 因为先算出来的是低位（个位），要到最后才能拼出最高位，所以每次把新的余数拼到字符串的最前面。

参考代码

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

int main() {
    string s;
    long long n;
    cin >> n;

    while (n) {
        int x = n % 8;          // 余数
        s = char(x + '0') + s;  // 拼到最前面
        n = n / 8;              // 继续除
    }

    cout << s;
    return 0;
}

复杂度分析

• 时间复杂度：O(log N)，每次除以 8
• 空间复杂度：O(log N)，存结果字符串