第一题：进制减半——数字魔法转换器

一、故事背景：数字王国的翻译任务

想象一下，我们生活在一个十进制王国。

平常使用的数字是：

0、1、2、3、4、5、6、7、8、9

但是，数字王国里还有其他进制的居民。

例如：

• 二进制：只有0和1。

• 八进制：使用0～7。

• 十进制：使用0～9。

• 十六进制：使用0～9和A～F。

现在，国王给了我们一个任务：

把一个以 m * n 为进制的数字，转换成以 n为进制的数字。

原题将这个转换称为“进制减半”，并要求按照从高位到低位的顺序输入各个数位。

举个例子

假设：

n = 2 m = 2

那么原来的进制就是：

m*n = 2*2 = 4

也就是说，我们要把一个四进制数转换成二进制数。

例如四进制数：

123

它表示：

而27的二进制表示是：

11011

所以：

四进制 123 = 二进制 11011

这就是我们要完成的魔法。

二、为什么不能直接使用普通整数？

原题给出的数字最多有18位，而且可能超过普通整数类型的表示范围。

所以程序没有直接把整个数字存进一个int或long long变量，而是采用了数组。

程序的核心数组是：

long long b[N];

我们可以把它想象成一排数字储物柜：

b[0] b[1] b[2] b[3] b[4] ...

每个格子保存一位数字。

注意：程序把最低位放在b[0]，而不是最高位。

例如：

数字：123

存入数组后：

这样设计有什么好处？

因为进制转换的过程中，需要反复进行除法和取余，而从最低位开始处理非常方便。

三、核心魔法：为什么要不断除以n？

我们先不看代码，理解数学原理。

假设有一个十进制数：

27

想把它转换成二进制。

不断除以2：

把余数从下往上读：

11011

这就是二进制结果。

因此，进制转换的基本思想是：

1. 不断除以目标进制。

2. 记录每次除法的余数。

3. 当商变成0时停止。

4. 把余数倒过来读。

但是原题的数字可能非常大，不能直接使用普通整数进行除法。

所以程序采用一种更巧妙的方法：

把原来的每一位数字保存到数组中，再模拟“整个数除以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; }

我们先抓住整个程序的主线：

读入一位原数 → 更新数组 → 对整个数组进行除法处理 → 去掉前导零 → 输出结果。

下面逐个填空。

五、第34题：①处应该填什么？

原题选项：

A.b[j] * n

B.b[j] * m

C.b[j - 1] * n

D.b[j - 1] * m

1. 先看这段代码

for (int j = len; j >= 1; j--) b[j] = ①;

它的作用是什么？

每次读入一个新的数位后，程序需要把原来保存的数字整体向高位移动一格，再把新读入的数位放到最低位。

例如原来数组保存：

b[2] b[1] b[0] 1 2 3

现在读入新数位4。

我们需要得到：

b[3] b[2] b[1] b[0] 1 2 3 4

注意数组实际是倒着保存的，所以原来的每个数位都要向更大的下标移动一格。

2. 应该怎样移动？

原来：

b[2] = 1; b[1] = 2; b[0] = 3;

移动后：

b[3] = b[2]; b[2] = b[1]; b[1] = b[0];

因此，正确的移动方式是：

b[j] = b[j - 1] ;

答案

第34题：D、b[j - 1] * m

输入的是 m*n 进制的，要转换成n进制的,所以要乘 m.

记忆口诀

数组整体向高位移动：

b[j] = b[j - 1] ;

就是把前一个格子的内容搬到后一个格子里。

六、第35题：②处应该填什么？

原题选项：

A.x * n

B.x

C.0

D.m

1. 看看新读入的数字放在哪里

代码：

b[0] = ②;

我们刚才已经知道：

• 原来的数字整体向高位移动。

• 新读入的数位应该放在最低位，也就是b[0]。

假设刚刚读入：

x = 7

那么最低位就应该保存7。

因此：

b[0] = x;

答案

第35题：B。

记忆口诀

新数字放最低位：

b[0] = x;

七、第36题：③处应该填什么？

原题选项：

A.b[j] / m

B.b[j] % n

C.b[j] % m

D.b[j] / n

1. 先理解数组中的进位

我们要把一个数转换成n进制。

在n进制中，每一位只能是：

0、1、2、……、n-1

如果某一位达到n或超过n，就必须向高位进位。

例如，在二进制中：

2 = 10（二进制）

所以：

当前位留下0 向高位进1

对于一般的n进制：

当前位的数值 = 原数值 % n 进位 = 原数值 / n

2. 看看原题代码

if (b[j] >= n) { b[j + 1] += ③; b[j] = ④; }

其中：

b[j + 1] += ③;

是把进位加到更高一位。

因此，③应该计算：

当前数位能够向高位贡献多少个n。

也就是：

b[j] / n

答案

第36题：D。

八、第37题：④处应该填什么？

原题选项：

A.b[j] / m

B.b[j] % n

C.b[j] % m

D.b[j] / n

1. 当前位需要留下什么？

假设我们正在处理一个二进制数位。

当前格子里有：

b[j] = 5

二进制中：

5 = 101（二进制）

所以：

当前位留下1 向高位进2

一般情况下：

当前位留下 b[j] % n

进位则是：

b[j] / n

因此：

b[j] = b[j] % n;

答案

第37题：B。

记忆口诀

进制转换中的除法与取余：

进位 = b[j] / n; 当前位 = b[j] % n;

这与十进制竖式加法中的“满十进一”是同一个思想，只不过这里变成了“满n进一”。

九、第38题：⑤处应该填什么？

原题选项：

A.len > 0 && b[len - 1] == 0

B.len > 0 && b[0] == 0

C.len > 1 && b[len - 1] == 0

D.len > 1 && b[0] == 0

1. 为什么需要删除前导零？

例如，某个结果在数组中保存为：

b[3] = 0 b[2] = 0 b[1] = 1 b[0] = 1

从高位到低位输出：

0011

但是我们通常希望输出：

11

因此，程序需要把最高位多余的0去掉。

2. 最高位在哪里？

由于数组是倒着保存的：

b[0]：最低位 b[1]：次低位 b[2]：更高位 ……

所以当前最高位是：

b[len - 1]

如果它等于0，就可以把长度减1：

len--;

3. 为什么必须保证len > 1？

假设转换结果是0。

如果不限制长度，程序可能不断删除最高位，最后长度变成0，导致输出循环无法正确输出一个0。

因此必须保留至少一位。

正确条件是：

len > 1 && b[len - 1] == 0

答案

第38题：C。

十、第一题完整答案与代码

答案汇总

填空后的完整程序

#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[j - 1] * m; b[0] = x; len++; for (int j = 0; j < len; j++) if (b[j] >= n) { b[j + 1] += b[j] / n; b[j] = b[j] % n; if (j + 1 == len) len++; } } while (len > 1 && b[len - 1] == 0) len--; for (int i = len - 1; i >= 0; i--) std::cout << b[i] << ' '; return 0; }

第一题通关口诀

先整体乘m，再加新数位；
满n就进位，余数留当前；
最后去前导零，从高位向低位输出。