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

30000 -2

输出 #1

30000=11011010101110000(base-2)

输入输出样例 #2

输入 #2

-20000 -2

输出 #2

-20000=1111011000100000(base-2)

输入输出样例 #3

输入 #3

28800 -16

输出 #3

28800=19180(base-16)

输入输出样例 #4

输入 #4

-25000 -16

输出 #4

-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$ 。

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

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

2. 算法流程

处理0的特判：如果输入的十进制数 $n$ 一开始就是 0，直接输出其基数的 0 即可，但根据本题数据测试，我们可以将其整合到正常逻辑中，或者短除时循环至少执行一次。我们通常使用递归或栈来将得到的余数倒序输出。
短除法运算（递归或迭代）：
- 当 $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$ ，继续循环或递归。
输出格式：将得到的字符串倒序输出，格式要求严格：${原始n}=${结果}(base${R})。

3. 核心要点总结

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

示例代码

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

#include <iostream>
#include <string>

// 数字到字符的映射表，最大处理至36进制 (问题中|R|<=20，这里给全足够)
const std::string P = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// 递归进行进制转换输出
void transform(int n, int r) {
    if (n == 0) {
        return; // 除到商为0，结束递归
    }

    int remain = n % r; // 计算余数
    int quotient = n / r; // 计算商

    // 如果余数小于0，修正为正整数范围 [0, |r|-1]
    if (remain < 0) {
        remain -= r;    // 相当于加上进制数r的绝对值
        quotient++;     // 为了保持等式成立，商加1
    }

    // 递归处理之后的商 (不断往高位递归)
    transform(quotient, r);

    // 递归回溯阶段打出对应位上的字符，巧妙实现倒序输出
    std::cout << P[remain];
}

int main() {
    // 优化输入输出流
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, r;
    // 读取十进制数 n 和负进制数的基数 r
    std::cin >> n >> r;
    std::cout << n << "="; // 输出原始值及等号

    // 特判，如果数字一开始就是 0，结果为 0
    if (n == 0) {
        std::cout << 0;
    } else {
        // 调用递归函数输出进制转换结果
        transform(n, r);
    }

    // 按题目要求的后缀格式输出基数
    std::cout << "(base" << r << ")\n";

    return 0;
}

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

#include <iostream>
#include <string>
#include <algorithm>

// 数字到字符的映射表
const std::string P = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
    // 优化输入输出流
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, r;
    std::cin >> n >> r;
    std::cout << n << "=";

    if (n == 0) {
        std::cout << 0;
    } else {
        std::string ans = "";
        int temp = n; // 保留原值，用临时变量递推

        // 迭代进行短除法计算
        while (temp != 0) {
            int remain = temp % r;
            int quotient = temp / r;

            // 将负数余数转化为正数，同时商进位
            if (remain < 0) {
                remain -= r;
                quotient++;
            }

            // 把每一位余数映射成对应字符并拼接到字符串中
            ans += P[remain];
            temp = quotient;  // 更新商
        }

        // 短除法得到的是反序的，这里将其翻转为正序（高位在前）
        std::reverse(ans.begin(), ans.end());
        // 输出得到的结果
        std::cout << ans;
    }

    // 输出题目要求的基数格式
    std::cout << "(base" << r << ")\n";

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年3月20日