【NOIP】2000真题解析 luogu-P1017 进制转换

NOIP 2000真题，负进制转换原理与实现，重点理解C++中取模运算的特性。GESP 五、六级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P1017 [NOIP 2000 提高组] 进制转换

题目要求

题目描述

我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以 $10$ 为底数的幂之和的形式。例如 $123$ 可表示为 $1 \times 10^2+2\times 10^1+3\times 10^0$ 这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数，以 $2$ 为底数的幂之和的形式。

一般说来，任何一个正整数 $R$ 或一个负整数 $-R$ 都可以被选来作为一个数制系统的基数。如果是以 $R$ 或 $-R$ 为基数，则需要用到的数码为 $0,1,\dots,R-1$。

例如当 $R=7$ 时,所需用到的数码是 $0,1,2,3,4,5,6$，这与其是 $R$ 或 $-R$ 无关。如果作为基数的数绝对值超过 $10$，则为了表示这些数码，通常使用英文字母来表示那些大于 $9$ 的数码。例如对 $16$ 进制数来说,用 $A$ 表示 $10$，用 $B$ 表示 $11$，用 $C$ 表示 $12$，以此类推。

在负进制数中是用 $-R$ 作为基数，例如 $-15$（十进制）相当于 $(110001)_{-2}$（$-2$进制），并且它可以被表示为 $2$ 的幂级数的和数：

$(110001)_{-2}=1\times (-2)^5+1\times (-2)^4+0\times (-2)^3+0\times (-2)^2+0\times (-2)^1 +1\times (-2)^0$

设计一个程序，读入一个十进制数和一个负进制数的基数，并将此十进制数转换为此负进制下的数。

输入格式

输入的每行有两个输入数据。

第一个是十进制数 $n$。第二个是负进制数的基数 $R$。

输出格式

输出此负进制数及其基数，若此基数的绝对值超过 $10$，则参照 $16$ 进制的方式处理。

输入输出样例 #1

输入 #1

130000 -2

输出 #1

130000=11011010101110000(base-2)

输入输出样例 #2

输入 #2

1-20000 -2

输出 #2

1-20000=1111011000100000(base-2)

输入输出样例 #3

输入 #3

128800 -16

输出 #3

128800=19180(base-16)

输入输出样例 #4

输入 #4

1-25000 -16

输出 #4

1-25000=7FB8(base-16)

说明/提示

【数据范围】

对于 $100\%$ 的数据，$-20 \le R \le -2$，$|n| \le 37336$。

【题目来源】

NOIP 2000 提高组第一题

题目分析

1. 核心思路：短除法与负数取模

进制转换的通用解法是“短除法”：每次用被除数除以进制数（基数），把每一次得到的余数记录下来，作为新进制下的一位数字（从低位到高位），然后把商作为新的被除数，继续除以基数，直到商为 0。最后把取得的余数倒序排列即可。

负进制转换的核心思想仍然是“短除法”，但我们需要特别处理一个关键问题：C++ 中负数对负数取模，余数可能是一个负数。

例如，$-15 \div -2 = 7 \dots -1$。 在常规的数学进制表示中，这一位对应的余数作为“数码”，不可能是负数，必须是 $0, 1, 2, \dots, |R|-1$ 之间的正整数或零。而如果余数为负数，则不能直接作为计算结果的每一位输出。

解题策略：转化余数为正数

根据除法的定义：被除数 = 商 $\times$ 除数 + 余数

即：$n = q \times R + r$ （其中 $r$ 为余数，$q$ 为商）

当我们在 C++ 里计算 $n \pmod R$，如果余数 $r < 0$，我们要怎么把它变成正的呢？ 只要我们在算式中增加一个除数 $R$，再减去一个除数 $R$ 即可：

$n = q \times R + R - R + r$ $n = (q + 1) \times R + (r - R)$

我们知道 $R$ 是负数（如 $-2$），那么 $r - R$ 实际就相当于加上了负进制数的绝对值，此时新的余数 $r_{new} = r - R$ 就变成正数了。 为了保持等式成立，新的商变成了 $q_{new} = q + 1$。

通过这种“借位”的思想，若遇到负数的余数，我们可以：

1. 余数 减去基数 R（相当于加上 $|R|$），成为正数。
2. 商 加 1，继续下一步的短除。

2. 算法流程

1. 处理0的特判：如果输入的十进制数 $n$ 一开始就是 0，直接输出其基数的 0 即可，但根据本题数据测试，我们可以将其整合到正常逻辑中，或者短除时循环至少执行一次。我们通常使用递归或栈来将得到的余数倒序输出。
2. 短除法运算（递归或迭代）：
   • 当 $n \ne 0$ 时，计算商 $q = n / R$ 和余数 $r = n \pmod R$。
   • 如果余数 $r < 0$，按照我们的调整策略，让 $r = r - R$，同时让 $q = q + 1$。
   • 记录此余数对应在数码表中的字符。我们需要准备一个包含 0-9 和 A-J 的字符数组，以便可以查询任意正数在特定进制（最高到 20 进制）下的代表字母。本题绝对值最高到 20，因此准备充足的字符映射足以应对。
   • 更新 $n = q$，继续循环或递归。
3. 输出格式：将得到的字符串倒序输出，格式要求严格：${原始n}=${结果}(base${R})。

3. 核心要点总结

• C++ 取模机制： C++ 中取模运算 -15 % -2 的结果是 -1。理解并处理这种语言特性的直接行为，是做这类问题的基础。
• 借位调整策略： 如果余数为负数，必须通过 余数 -= 进制， 商 += 1 的方式将其转正。
• 倒序转换特性： 短除法求出的第一个余数是数字的最低位代码，最后一次得到的余数是最高位。这里可以使用递归巧妙地倒置输出，或者将每次得到的字母存入字符串，最后进行reverse。
• 数字对应的字符： 当除数绝对值大于 10 时，余数可能是 10, 11... 我们需要建立字符映射表，根据下标快速获取正确的那个英文字母。

示例代码

方案一：使用递归实现，代码更简洁

1#include <iostream>
2#include <string>
3
4// 数字到字符的映射表，最大处理至36进制 (问题中|R|<=20，这里给全足够)
5const std::string P = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
6
7// 递归进行进制转换输出
8void transform(int n, int r) {
9    if (n == 0) {
10        return; // 除到商为0，结束递归
11    }
12
13    int remain = n % r; // 计算余数
14    int quotient = n / r; // 计算商
15
16    // 如果余数小于0，修正为正整数范围 [0, |r|-1]
17    if (remain < 0) {
18        remain -= r;    // 相当于加上进制数r的绝对值
19        quotient++;     // 为了保持等式成立，商加1
20    }
21
22    // 递归处理之后的商 (不断往高位递归)
23    transform(quotient, r);
24
25    // 递归回溯阶段打出对应位上的字符，巧妙实现倒序输出
26    std::cout << P[remain];
27}
28
29int main() {
30    // 优化输入输出流
31    std::ios_base::sync_with_stdio(false);
32    std::cin.tie(NULL);
33
34    int n, r;
35    // 读取十进制数 n 和负进制数的基数 r
36    std::cin >> n >> r;
37    std::cout << n << "="; // 输出原始值及等号
38
39    // 特判，如果数字一开始就是 0，结果为 0
40    if (n == 0) {
41        std::cout << 0;
42    } else {
43        // 调用递归函数输出进制转换结果
44        transform(n, r);
45    }
46
47    // 按题目要求的后缀格式输出基数
48    std::cout << "(base" << r << ")\n";
49
50    return 0;
51}

方案二：使用循环和字符串翻转实现

1#include <iostream>
2#include <string>
3#include <algorithm>
4
5// 数字到字符的映射表
6const std::string P = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
7
8int main() {
9    // 优化输入输出流
10    std::ios_base::sync_with_stdio(false);
11    std::cin.tie(NULL);
12
13    int n, r;
14    std::cin >> n >> r;
15    std::cout << n << "=";
16
17    if (n == 0) {
18        std::cout << 0;
19    } else {
20        std::string ans = "";
21        int temp = n; // 保留原值，用临时变量递推
22
23        // 迭代进行短除法计算
24        while (temp != 0) {
25            int remain = temp % r;
26            int quotient = temp / r;
27
28            // 将负数余数转化为正数，同时商进位
29            if (remain < 0) {
30                remain -= r;
31                quotient++;
32            }
33
34            // 把每一位余数映射成对应字符并拼接到字符串中
35            ans += P[remain];
36            temp = quotient;  // 更新商
37        }
38
39        // 短除法得到的是反序的，这里将其翻转为正序（高位在前）
40        std::reverse(ans.begin(), ans.end());
41        // 输出得到的结果
42        std::cout << ans;
43    }
44
45    // 输出题目要求的基数格式
46    std::cout << "(base" << r << ")\n";
47
48    return 0;
49}