[NOIP 2000 提高组] 进制转换

GitHub跳转原题关系图返回列表

每次选择非负余数并据此更新负进制商，逆序连接余数得到表示。

OJ: luogu

题目 ID: P1017

难度:普及/提高-

标签:负进制进制转换整除python

日期: 2026-07-16 19:20

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

把十进制整数 n 转成基数 R 的负进制表示，其中 -20<=R<=-2，数码必须在 0..|R|-1。

思路

每一步需要满足 value=quotient*base+remainder，并让余数非负。取 remainder=value%(-base)，它一定落在 0..|base|-1，再计算：

text
quotient=(value-remainder)//base

重复到商为零。余数仍按低位到高位产生，最后反转。原数为零时表示为 0。

Python 知识

  • Python 的 % 与 // 遵守整除恒等式，但负除数余数符号不适合本题，因此主动对 -base 取模。
  • f-string 直接拼出题目要求的 n=result(baseR) 格式。
  • 字符表扩展到 J，覆盖绝对值不超过 20 的基数。
  • reversed 惰性反转数码列表。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：负数整除与取模语义。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字符串构造。

代码

python
import sys


DIGITS = "0123456789ABCDEFGHIJ"


def main():
    original, base = map(int, sys.stdin.buffer.read().split())
    value = original
    converted = []

    if value == 0:
        converted.append("0")
    while value:
        remainder = value % (-base)
        value = (value - remainder) // base
        converted.append(DIGITS[remainder])

    print(f"{original}={''.join(reversed(converted))}(base{base})")


if __name__ == "__main__":
    main()
cpp
/**
 * P1017 [NOIP2000 提高组] 进制转换
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const char DIGITS[] = "0123456789ABCDEFGHIJ";

int main() {
    int n, base;
    scanf("%d%d", &n, &base);
    printf("%d=", n);
    char ans[40];
    int len = 0;
    if (n == 0) ans[len++] = '0';
    while (n) {
        int r = n % base;         // C++ 中 n % 负数 可能为负
        if (r < 0) r -= base;     // 调整余数为非负
        n = (n - r) / base;       // 重新计算商
        ans[len++] = DIGITS[r];
    }
    for (int i = len - 1; i >= 0; --i) putchar(ans[i]);
    printf("(base%d)\n", base);
    return 0;
}

复杂度

设结果有 d 位，时间复杂度 O(d)O(d)，空间复杂度 O(d)O(d)。

总结

负进制转换的关键不是照搬 divmod(value,base)，而是先保证余数属于合法的非负数码范围。