形式化题目

数位集合是 62 个字符 0-9A-Za-z，其权值依次为 $0,1,\dots,61$。给定 $T$ 组数据， 第 $i$ 组给出源进制 $b$（$2 \leqslant b \leqslant 62$）、目标进制 $c$（$2 \leqslant c \leqslant 62$）， 以及一个用 $b$ 进制写出的数位串 $s = s_1 s_2 \dots s_n$（$s_j$ 表示权值 $a_j \in [0, b)$； $s_1$ 不是字符 0，除非 $s$ 本身就是单个 0）。它代表的整数是

要求对每组求出唯一的数位串 $t = t_1 t_2 \dots t_m$（权值 $d_j \in [0, c)$，且 $t_1$ 不是字符 0， 除非 $N = 0$），使得

即把同一个整数从 $b$ 进制改写成 $c$ 进制。$N = 0$ 时规定 $t$ 就是单个字符 0。

数据中最长的输入是 10 进制 109 位、62 进制 62 位；数值本身最大约 $62^{62} \approx 10^{111}$， 远超 64 位整数范围。

正解

思路

朴素想法：把整个数按“每位乘以 $b$ 再累加”的 Horner 法在机器整数里求值，再反复取模 输出。数据里 $N$ 有 111 个十进制位，装不进 long long，所以这条路在 C++ 里走不通； 换成任意精度整数又等于绕开了本题要练的东西。于是只能把整数本身存成数位数组， 在数组上做算术。

关键观察一：整道题只需要一个原子操作。 输入串本身就是 $b$ 进制数位，读入只是一次查表， 不必求值；要得到 $c$ 进制表示，需要的只是“把当前的 $N$ 除以 $c$ 的商和余数”。 而长除法正好给出这两个量：设当前下落进位为 $rem$，从左到右扫过数位 $a_j$，则

关键观察二：中间量不会溢出。 归纳可知始终有 $rem < c \leqslant 62$， 而 $a_j < b \leqslant 62$，所以 $x \leqslant 61 \times 62 + 61 = 3843$，普通 int 就够用。 这也是本题不需要写完整高精度库的原因——只需要一次 $O(n)$ 的除法。

关键观察三：第一次除法得到的是最低位。 由 $N = cQ + r$ 可知 $r = N \bmod c$ 恰是 $N$ 在 $c$ 进制下的最后一位，商 $Q$ 则是它的前缀。把 $N$ 换成 $Q$ 重复下去， 收集到的余数就是从低到高的数位，最后翻转即可。

算法流程：

1. 把输入串逐字符查表，得到源进制下的数位数组 digits（高位在前）；
2. 循环：digits, rem = divide(digits, b, c)，把 rem 收进结果；
3. digits 变空时停止（说明已经除尽），把结果翻转拼接；若结果为空则原数是 0，输出 0。

样例推演：取第 1 组 62 2 abcdefghiz，数位是 [36, 37, 38, 39, 40, 41, 42, 43, 44, 61]。下表是第一次除以 $c = 2$ 的逐位过程 （x = rem*62 + a，商位为 x // 2，新进位为 x % 2）：

（表中“进位 $rem$”一行是处理该位之前的进位，它等于上一步的新进位。）

第一次除法结束时进位为 $1$，这就是最低二进制位；商数组变成 [18,18,50,19,51,20,52,21,53,30]，第二轮继续同样地扫一遍。共做 59 轮，把 59 个余数 从后往前读，得到样例输出中的

111011100000100010111110010010110011111001001100011010010001

注意当商位为 $0$ 而商数组还是空的时候必须跳过（这只可能出现在商的最高位一侧）， 否则会留下前导零；而 $N = 0$ 的用例（如 2 3 0）第一轮商就为空，直接输出 0。

代码

Python 版：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54#!/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-01 11:03
# update_at: 2026-10-01 11:03

import sys

DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"  # 62 个数位，下标即权值
VALUE = {ch: v for v, ch in enumerate(DIGITS)}


def divide(digits: list[int], base: int, divisor: int) -> tuple[list[int], int]:
    """对源进制数位表做一次长除法，返回 (商的高位到低位, 余数)。

    手算长除法：把下落进位 rem 与当前位拼成 x = rem*base + a，商位取 x // divisor。
    rem < divisor ≤ 62 且 base ≤ 62，所以 x < 3900，C++ 里用 int 也不会溢出。
    """
    quotient: list[int] = []
    rem = 0
    for a in digits:
        x = rem * base + a
        digit = x // divisor
        if quotient or digit:  # 忽略前导零；商为空说明已经除尽
            quotient.append(digit)
        rem = x % divisor
    return quotient, rem


def convert(digits: list[int], base: int, target: int) -> str:
    """把源进制数位表写成目标进制字符串：反复除 target，余数就是低位到高位。"""
    out: list[str] = []
    while digits:
        digits, rem = divide(digits, base, target)
        out.append(DIGITS[rem])  # 余数必落在 [0, target)，正是目标进制的一位
    return "".join(reversed(out)) or "0"  # 商被除空说明原数是 0


def solve() -> None:
    # 三列里混着非数值的数位串，不能整体 map(int)，所以只对数值位置套 int(next(data))
    data = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    T = int(next(data))  # 组数
    for _ in range(T):
        src, dst = int(next(data)), int(next(data))  # 源进制、目标进制
        raw = next(data)  # 源进制数位串，保持 bytes 直接当数位表用
        digits = [VALUE[chr(ch)] for ch in raw]  # 输入数自己就是源进制的数位表
        out += [f"{src} {raw.decode()}", f"{dst} {convert(digits, src, dst)}", ""]
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * 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-06 14:55
 * update_at: 2026-10-06 14:55
 */

// main.cpp：把 62 进制数位串在任意两种进制之间转换。
// 数值最大约 62^62，装不进 long long，所以把整数存成数位数组，
// 只需要一种原子操作：数位的长除法（除以目标进制 c，同时得到商和余数）。

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>

typedef long long ll;

const ll MAXL = 200;  // 输入串最长约 109 位，开 200 足够

// 62 个数位字符：'0'-'9' 权值 0-9，'A'-'Z' 权值 10-35，'a'-'z' 权值 36-61
const char DIGITS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

ll T;
ll base;                 // 源进制 b
ll target;               // 目标进制 c
ll digits[MAXL + 5];     // 当前数位数组（高位在前），每次长除法后变成商
ll q[MAXL + 5];          // 长除法的临时商数组
ll len;                  // digits 当前的位数
std::string out;         // 收集到的余数，即目标进制的数位（从低到高）

// 按字符查它在 62 个数位里的权值，不在集合里返回 -1
ll char_value(char ch) {
    for (ll i = 0; i < 62; i++)
        if (DIGITS[i] == ch) return i;
    return -1;
}

// 把数位 digits（共 len 位，基数为 base）除以 div，就地更新为商，
// 返回余数；除完跳过商的前导零，len 变成商的实际位数。
ll divide_small(ll div) {
    ll rem = 0;  // 从高位往低位下落的进位，始终小于 div <= 62
    for (ll i = 1; i <= len; i++) {
        ll x = rem * base + digits[i];  // x 最大 61*62+61 = 3843，int 都够
        q[i] = x / div;
        rem = x % div;
    }
    // 找商的第一个非零位；商可能全零（此时余数就是原数本身取模）
    ll first = 1;
    while (first <= len && q[first] == 0) first++;
    ll new_len = len - (first - 1);  // 商的位数（可能为 0）
    for (ll i = 1; i <= new_len; i++)
        digits[i] = q[first + i - 1];
    len = new_len;
    return rem;
}

// 反复长除法：每轮余数是目标进制的最低一位，逆序拼出答案
std::string convert() {
    out.clear();
    while (len > 0) {
        ll rem = divide_small(target);
        out += DIGITS[rem];
    }
    std::string res;
    for (ll i = (ll)out.size() - 1; i >= 0; i--)  // 余数从低到高，翻转
        res += out[i];
    if (res.empty()) res = "0";  // 原数就是 0
    return res;
}

void solve() {
    scanf("%lld", &T);
    while (T--) {
        char str[MAXL + 5];
        scanf("%lld %lld %s", &base, &target, str);
        len = strlen(str);
        for (ll i = 0; i < len; i++)  // 高位在前，直接查表得到数位
            digits[i + 1] = char_value(str[i]);

        std::string ans = convert();
        printf("%lld %s\n", base, str);        // 第一行：源进制与原数
        printf("%lld %s\n\n", target, ans.c_str());  // 第二行：目标进制与新数，第三行为空行
    }
}

int main() {
    solve();
    return 0;
}

divide 只回答“这张数位数组除以 $c$ 之后的商和余数各是多少”，convert 只回答“把余数 从低到高收集起来是什么”，solve 只负责读入三列、原样回显输入数字、按三行一组输出。 源进制 base 只在 divide 内部用作拼接基数，除数是目标进制 target，两者不要写反。

复杂度

设输入数在源进制下有 $n$ 位、在目标进制下有 $m$ 位。每轮长除法 $O(n)$，共 $m$ 轮：

• 时间：$O(n \cdot m)$。因为 $m = \Theta\!\left(n \cdot \frac{\log b}{\log c}\right)$， 即 $O\!\left(n^2 \cdot \frac{\log b}{\log c}\right)$，与“手写高精度 + 逐位除法”的经典 做法同阶；最坏情形是 $b = 62$、$c = 2$，此时 $m$ 可达 $6n$ 左右。
• 空间：数位数组、商数组与输出串各 $O(n)$，合计 $O(n + m)$。

实测 84 组数据（含 62 进制 62 位、10 进制 109 位的最坏用例）总耗时 $0.018$ s、 峰值内存 $14.7$ MB，远低于 $1000$ ms / $128$ MB 的限制。

总结

本题的解法只有一句话：要转成 $c$ 进制，就不断除以 $c$，把余数从后往前收集。 真正需要解决的问题是“在没有大整数类型的语言里怎么除”，答案是用数位数组做长除法， 并注意长除法的中间量 $x = rem \cdot b + a_j$ 最大只有 $61 \times 62 + 61 = 3843$。

由此可以推广出两条实用的经验：

1. 判断高精度题是否需要完整的高精度库——如果全程只用到“乘以 $b$ 加一位”和 “除以某个小常数取余”，那么两个 $O(n)$ 的手写循环就够了，不必实现乘除法。
2. 读入（Horner 求值）与输出（反复取余）是一对逆过程；凡是“把一个数从一种基换到 另一种基”的问题，输入按基展开、输出按基取余，一般都能把复杂度压到 $O(nm)$。

图示解析

下图给出从题面到输出的完整主线：左侧是输入提供的原始信息，中间是唯一需要自己实现的 一次长除法，右侧是收集与拼接的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17输入：b, c, s = s_1 s_2 ... s_n
   │   s_j 查表得权值 a_j，直接得到 b 进制的数位数组（不必求值）
   ▼
digits = [a_1, a_2, ..., a_n]       高位在前
   │
   │   循环 m 次 ──────────────────────────────────────────┐
   │   rem = 0                                             │
   │   for a in digits:                                    │
   │       x = rem*b + a        # x ≤ 61*62+61 = 3843      │
   │       q.append(x // c)     # 商位，跳过商的前导零      │
   │       rem = x % c          # 新的下落进位             │
   │   digits = q                                          │
   │   out.append(DIGITS[rem])  # 余数 = c 进制的一位      │
   │   ──────────────────────────────────────────────────┘
   │   digits 为空 ⇒ 已除尽
   ▼
"".join(reversed(out))  或  "0"（out 为空时）

关键在中间那个循环体：它同时产出两样东西——商回到 digits 继续下一轮， 余数进入 out 成为结果的低位。因此 out 天然是逆序的，最后一步翻转是必需的； 而 out 为空则说明原数就是 $0$，这也是唯一需要特判的情形。