题解

第一步：原进制转十进制

从左到右扫描字符串，使用：

value = value * n + 当前数码值

第二步：十进制转目标进制

不断执行：

余数 = value % m
value = value / m

得到的余数顺序是从低位到高位，因此先保存，再反转输出。

数码 $10\sim15$ 要转换为 A 到 F。

正确性说明

第一步根据进制位权递推，得到原数的准确十进制值。第二步利用除基取余法：每次余数恰好是当前最低位数码，除以目标进制后继续处理更高位。逆序输出所有余数，即得到目标进制表示。

复杂度

设输入长度为 $L$，输出长度为 $R$：

• 时间复杂度：$O(L+R)$；
• 空间复杂度：$O(R)$。