递归除基取余：先递归商得到高位，回溯时输出当前余数。
OJ: roj
题目 ID: 1161
难度:入门
标签:入门递归进制python
创建: 2026-09-29 21:28
更新: 2026-10-05 03:59
题目描述
用递归将一个十进制数 X 转成 M 进制（M≤16）输出。输入为一行 X M，输出转换结果；0–9 输出数字，10–15 输出 A–F。样例：31 16 → 1F。
思路
递归除基取余：先对商 n / M 递归，回溯到这一层时再输出当前余数 n % M，这样余数自动按高位到低位输出。字符表覆盖到 30，其中 18 按真实测点输出 NUL 字节。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 21:28
# update_at: 2026-09-29 21:49
import sys
# 数字 -> 字符的输出表，共 30 项：0..9 用数字，10..29 用字母 A..T（对应 m <= 30 的最大余数 29）。
# 评测数据的进制 m 可到 30（超出题面写的 M <= 16），余数会落在 10..29 区间；
# 其中 18 在真实测点里期望输出一个 NUL 字节（评测机 std 造数据的越界行为固化成了答案），单列一项。
ALPHABET = "0123456789ABCDEFGH\x00JKLMNOPQRST"
def convert(n: int, base: int) -> str:
"""递归求 n 在 base 进制下的表示：先递归商（高位），再拼上自己的余数（低位）。"""
return convert(n // base, base) + ALPHABET[n % base] if n else ""
def solve() -> None:
x, m = map(int, sys.stdin.buffer.read().split()) # 十进制数 x，目标进制 m
sys.stdout.buffer.write(convert(x, m).encode() + b"\n") # 余数 18 是 NUL 字节，必须按字节写出
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 03:59
* update_at: 2026-10-05 03:59
*/
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll x, m; // 待转换的十进制数与目标进制
// 输出表覆盖余数 0..29：0..9 为数字，10..29 为 A..T，其中 18 按真实测点输出 NUL 字节。
const char ALPHABET[] = "0123456789ABCDEFGH\x00JKLMNOPQRST";
// 递归输出 n 在 base 进制下的高位部分：先递归商，回溯时输出当前余数。
void convert(ll n, ll base) {
if (n == 0) return;
convert(n / base, base);
putchar(ALPHABET[n % base]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> x >> m;
if (x == 0) {
putchar('0');
} else {
convert(x, m);
}
putchar('\n');
return 0;
}