CSP-J 2026 第一轮 第 34 题：进制减半：①处应填

题目

给定 $n, m$，再给定一个 $mn$ 进制下的数 $A$，其各个数位上的数按照从高位到低位的顺序给出，请你将其转化为 $n$ 进制，并同样按照从高位到低位的顺序输出。

输入的第一行依次为 $n, m$ 和 $A$ 的位数 $d$，接下来 $d$ 个数 $a_{d}, a_{d - 1}, … , a_{1}$ 从高位到低位描述各个数位上的数。

数据满足 $2 \le n, m \le 10$，$1 \le d \le 18$，$0 \le A < 2^{63}$；对于所有 $1 \le i \le d$，$0 \le a_{i}< mn$。

以下程序按“逐位除以 $n$”的方法完成进制转换。请补全程序。

#include <iostream>

constexpr int N = 100005;
long long b[N];

int main() {
    long long n, m, d;
    std::cin >> n >> m >> d;
    int len = 1;
    for (int i = 0; i < d; i++) {
        long long x;
        std::cin >> x;
        for (int j = len; j >= 1; j--)
            b[j] = /* ① */;
        b[0] = /* ② */;
        len++;
        for (int j = 0; j < len; j++)
            if (b[j] >= n) {
                b[j + 1] += /* ③ */;
                b[j] = /* ④ */;
                if (j + 1 == len) len++;
            }
    }
    while (/* ⑤ */) len--;
    for (int i = len - 1; i >= 0; i--)
        std::cout << b[i] << ' ';
    return 0;
}

①处应填（ ）。

选项

• A. b[j] * n
• B. b[j] * m
• C. b[j - 1] * n
• D. b[j - 1] * m

答案

D

题解

应选 **D．b[j - 1] * m**。

数组 b 按低位到高位存储当前数的 \(n\) 进制数位。每读入一个新的 \(mn\) 进制数位 x，当前数就要更新为： \[ \text{新值}=\text{原值}\times(mn)+x. \]

在 \(n\) 进制下，乘以 \(mn\) 可以拆成两步：

• 乘以 \(n\)：所有数位向高位移动一位，所以 b[j] 取自 b[j - 1]。
• 乘以 \(m\)：移动后的数位再乘以 m，随后由程序统一处理进位。

因此①应填： ``cpp b[j - 1] * m ``

循环从高位向低位执行，是为了避免覆盖尚未使用的原数位。