形式化题目

给定 $n$ 个用例。每个用例给出字符串 $S$ 与进制 $a, b$（$a, b \in [2, 36]$），$S$ 是一个 $a$ 进制数，数符约定 0-9 表示 $0 \sim 9$、A-Z 依次表示 $10 \sim 35$。求与 $S$ 数值相等的 $b$ 进制表示，逐用例输出一行。

$S$ 按 $a$ 进制解析后的十进制值 $\leqslant 2^{63}-1$。

样例：123ABC 16 2 表示把 $16$ 进制的 123ABC 转成 $2$ 进制，输出 100100011101010111100。

正解

思路

进制表示的定义本身就是「按位权展开」：

所以任意两种进制互转的通用做法是拿十进制当桥梁，两段各自独立完成：

1. $a$ 进制 $\to$ 十进制：逐字符映射数位（0-9/A-Z → $0 \sim 35$），按权求和。Python 的内建 int(s, a) 恰好实现这一步，且天然支持 $2 \sim 36$ 进制与大写字母，与题面数符约定完全一致。
2. 十进制 $\to$ $b$ 进制：对 $v$ 反复 divmod(v, b)，每次余数就是当前最低位，商是剩余高位；循环取完后余数序列是低位到高位，倒序拼接即答案。

下面用样例展示两段的中间量（第一段按权求和，第二段除 $2$ 取余）：

表格前六行是第一段（按权求和得到十进制 $1194684$），后两行是第二段（除基取余得到 $2$ 进制）。观察重点：第一段每个数位只依赖「数值 × 权」，第二段每次只处理当前最低位——两段都是单向线性扫描，没有回溯，也没有跨用例共享状态。数值上界 $2^{63}-1$ 保证中间值 $v$ 最多 $63$ 个二进制位，因此单用例的两段工作量都是 $O(63)$ 量级，不存在需要特殊处理的「大数瓶颈」（Python 的 int 本身是任意精度）。

不需要按子任务分层：$30\%$ 的 $a,b \in \{2,10\}$、$60\%$ 的 $\{2,8,10,16\}$ 只是进制取值的特例，通用解法一遍覆盖全部约束，2/8/16 进制之间的位分组快转（$8=2^3$、$16=2^4$）虽然常数更小，但不改变复杂度阶，反而多出两套代码路径。

代码

1DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"  # 数符表：下标即位值，>=10 用大写字母

• DIGITS 把「位值 → 数符」的映射收成一张表，下标即数值，第二段直接查表。
• to_base(value, base) 实现除基取余；value == 0 显式返回 "0"，因为循环对 $0$ 不执行，否则会得到空串。
• solve() 用 iter(...split()) 流式取 token，int(s, a) 完成第一段解析，结果收集进 out 后一次性输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/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-10-02 16:22
# update_at: 2026-10-02 16:22

import sys

DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"  # 数符表：下标即位值，>=10 用大写字母


def to_base(value: int, base: int) -> str:
    """十进制整数转 base 进制字符串：反复除 base 取余，余数倒序即高位在前。"""
    if value == 0:
        return "0"
    out: list[str] = []
    while value:
        value, r = divmod(value, base)
        out.append(DIGITS[r])
    return "".join(reversed(out))


def solve() -> None:
    data = iter(sys.stdin.read().split())
    n = int(next(data))
    out: list[str] = []
    for _ in range(n):
        s = next(data)             # a 进制的原数
        a, b = int(next(data)), int(next(data))
        # int(s, a) 直接按 a 进制解析（0-9/A-Z 均支持），再压成 b 进制
        out.append(to_base(int(s, a), b))
    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

• 时间：设 $S$ 长度为 $k$、输出长度为 $L$。解析 $O(k)$，压位 $O(L)$，且 $k, L \leqslant 63$。单用例 $O(k+L)$，全体 $O(n(k+L))$，与 C++ 正解同阶（都是线性扫描两遍）。
• 空间：单用例 $O(k+L)$，输出缓冲累计 $O(\sum L) \leqslant 63n$ 字符，远低于 $128$MB 限制。

总结

• 任意进制互转的标准模型：以十进制为桥梁，「按权求和」进，「除基取余」出，两段各线性一遍。
• Python 落地时第一段直接用内建 int(s, a)（支持 $2 \sim 36$ 进制、0-9A-Z），只需手写第二段压位。
• 边界记忆：数值为 $0$ 时除基取余循环不执行，必须单独返回 "0"。
• 验证：真实数据 $10$ 组全部 PASS，单测例 $\leqslant 0.03$s、峰值内存 $\leqslant 18$MB。