负进制转换
内容纲要
负进制转换
题目描述
可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以 $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)Answer
这个处理方式针对于负进制转换中的一个关键点：当使用负数作为基数进行除法和取余数时，可能会出现余数为负的情况。但在进制转换中，希望所有的数字（包括余数）都是非负的，以便能够直接使用这些数字来表示最终的进制数。
关键点解释
在传统的正进制系统中（比如十进制转二进制），当对一个数进行除以基数的操作时，余数总是非负的，这是因为基数是正数，余数的范围是从0到基数-1。
然而，在负进制系统中，基数是负数，这意味着除法和余数操作的结果会有所不同。直接进行除法和取余操作可能得到一个负的余数，这并不适合直接用于进制转换表示。因此，需要调整余数和商，以确保余数是非负的，同时还要保持整个表达式的等价性。
为什么要这样做
保证余数非负：通过将负的余数调整为非负值（通过加上基数的绝对值），保证了进制转换中使用的每个数位都是一个有效的非负数码。
调整商：当调整余数以使其非负时，实际上是向当前的数位“借”了值。为了补偿这个“借”出的值，需要将商（即下一次迭代处理的数）适当增加。
具体例子
假设在将某个数转换为-2进制，遇到了一个负余数。如果不进行调整，直接使用负余数，那么这个负余数无法直接用于进制表示（因为进制数每位的数字应该是非负的）。通过增加基数的绝对值到余数（使余数非负）并适当调整商，确保了转换的正确性，同时保持了数学上的等价。
这种处理方式确保了在使用负基数进行进制转换时，所有的操作和结果都符合进制转换的规则和逻辑。
假设要将十进制数 $7$ 转换为 $-2$ 进制。基数是 $-2$，所以的目标是找到一个数，它的每一位乘以对应的 $(-2)^n$ 后，加和等于 $7$。
步骤1：初步除法和取余
首先，$7$ 除以 $-2$：
商为 $-3.5$，但只关心整数部分，所以商为 $-3$（向下取整）。
余数是 $1$。（因为 $7 = -2 \times (-3) + 1$）
这一步比较直接，没有遇到余数为负的情况。
步骤2：处理负商
接下来，对 $-3$ 重复这个过程：
$-3$ 除以 $-2$：
商为 $1.5$，整数部分为 $1$。
余数是 $-1$。（因为 $-3 = -2 \times 1 + (-1)$）
在这里，遇到了一个问题：余数为负 ($-1$)。但是在进制表示中，不能有负数的数位。因此，需要调整。
调整余数和商
为了得到一个非负的余数，可以将基数 $-2$ 的绝对值加到余数上，并相应地调整商：
新余数为 $1$（$-1 + |-2| = 1$）。
为了补偿这个调整，需要将商增加 $1$，所以新商为 $2$（原本为 $1$）。
继续转换过程
然后，对 $2$ 应用相同的转换逻辑：
$2$ 除以 $-2$ 得到商 $1$ 和余数 $0$。
$1$ 除以 $-2$ 得到商 $0$ 和余数 $1$（这是最后一步，因为商现在是 $0$）。
结果
将所有的余数放在一起，从最后的余数开始（这就是为什么需要反转字符串的原因），得到 $7$ 的 $-2$ 进制表示为 $1101$。
这个过程展示了当遇到负余数时，通过调整余数和商来确保所有数位都是非负的，同时也保持整个数学表达式的等价性。这样的调整对于负进制转换是必要的，以确保最终的进制数表示是正确和一致的。
为什么余数要加基数的绝对值，商加1
这个调整是为了保证余数始终为非负的，同时使得转换后的数学表达式仍然等价于原数。在负基数进制转换过程中，特别是当基数为负数时，按照标准的除法规则可能会导致余数为负数。为了避免这种情况，需要对余数进行调整，使其变为非负数，同时也要相应地调整商，以保证整个转换过程的正确性。来详细解释一下这个过程：
余数加基数的绝对值
当在负基数 $R$ 的情况下得到一个负余数时，这个余数是不符合进制转换的标准形式的，因为在进制表示中，每一位的数值应该是从0到基数的绝对值减一的非负整数。因此，为了将余数转换为一个合法的数位，需要将基数的绝对值加到这个负余数上。这样做的数学依据是：
$ \text{新余数} = \text{原余数} + |R| $
这样调整后的余数是满足进制转换条件的非负整数。
商加1的原因
当对余数进行调整，加上了基数的绝对值时，实际上在数学上是向更高位“借”了值。为了保持数的总值不变，需要相应地调整商。每当余数增加了基数的绝对值，实际上是增加了一个$R$的幂次到数的表示中。为了抵消这个增加的值，需要将商增加1，因为在下一轮计算中，这个增加的1会与基数$R$相乘，正好与向余数中添加的|R|相抵消。
这种调整确保了，即使在负基数下，也能正确地将十进制数转换为目标进制数，同时保持转换过程中每一步的等价性和数学上的准确性。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static String toNegativeBase(int n, int base) {
if (n == 0) {
return "0";
}
StringBuilder result = new StringBuilder();
while (n != 0) {
int remainder = n % base;
n /= base;
if (remainder < 0) {
remainder += Math.abs(base);
n += 1;
}
if (remainder >= 10) {
result.append((char) ('A' + (remainder - 10)));
} else {
result.append(remainder);
}
}
return result.reverse().toString();
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
System.out.println(n + "=" + toNegativeBase(n, r) + "(base" + r + ")");
}
}