CSP-J 入门级 · CSP 2026 入门级第一轮 第 19 题

【完善程序1】

（进制减半）给定 n, m，再给定一个 mn 进制下的数 A，其各个数位上的数按照从高位到低位的顺序给出，请你将其转化为 n 进制，并同样按照从高位到低位的顺序输出。输入的第一行依次为 n、m 和 A 的位数 d，接下来 d 个数 a_d, a_{d-1}, ..., a_1 从高位到低位描述各个数位上的数。数据满足 2 ≤ n, m ≤ 10，1 ≤ d ≤ 18，0 ≤ A < 2^63，对于所有 1 ≤ i ≤ d，0 ≤ 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;
}

mn进制转n进制：先整体×m再移位(×n)，进位除n取模n。

①下标j-1是旧值；⑤len>1防止删掉最后一位0。

考点：进制转换｜数组移位

程序在做什么

读入mn进制数位，每读一位先整体×m再移位(×n)，然后按n进制归一化进位。