题面
题目背景
NOIP2000 提高组 T1
题目描述
我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以 $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$。
题解
Q1: 负进制怎么求？
若对「负进制」不熟悉，一眼瞪出思路是不太可能的。
但是我们有两大法宝：「化未知为已知」和「特例入手」。
首先，联系已知：我们知道「短除法」可以进行十进制向$R$进制的转换，其中$R \ge 2，R \in N^*$。
然后，特例入手：我们尝试将${(14)}_{10}$转换成二进制数，过程如下：
14÷2=7……0 (Ⅰ)
7÷2=3……1 (Ⅱ)
3÷2=1……1 (Ⅲ)
1÷2=0……1 (Ⅳ)将上述各式的余数倒序（由$Ⅳ$至$Ⅰ$）写成一个二进制数，即得
${(14)}_{10}$=${(1110)}_{2}$
接着，尝试推广：将基数改为$-2$，再对${(14)}_{10}$进行一次短除法，会发生什么呢？
14÷(-2)=-7……0 (Ⅴ)
-7÷(-2)= 4……1 (Ⅵ)
4÷(-2)=-2……0 (Ⅶ)
-2÷(-2)= 1……0 (Ⅷ)
1÷(-2)= 0……1 (Ⅸ)将上述各式的余数倒序（由Ⅸ至Ⅴ）写成一个负二进制数，即得
${(14)}_{10}$=${(10010)}_{-2}$
验证一下：十进制下，我们有
$14=1×(-2)^4+0×(-2)^3+0×(-2)^2+1×(-2)^1+0×(-2)^0$
故依据不完全归纳法，尝试以此推广做题。总结一下，步骤是：
- 将十进制数$n$对$R$求模，存储余数
- 对$n$进行整数除法$n÷R$
- 循环以上过程，直到$n$的值为$0$
- 倒序输出所有余数
Q2: 负数取模，余数必非负吗？
我们通过一个简单的程序观察C++是如何处理负数取模的。
#include<cstdio>
int n,r;
int main()
{
scanf("%d%d",&n,&r);
printf("n/r=%d n%r=%d",n/r,n%r);
return 0;
} 输入$-7$ $-2$，输出如下：
n/r=3 n%r=-1但这与Q1中式($Ⅵ$)的结果$-7÷(-2)= 4 \cdots \cdots 1$略有出入。事实上，式($Ⅵ$)的处理默认了“余数为非负整数”的规则，这是因为余数与转换后数字的数位一一对应，而数位上的单个数字不能为负。
对比两种求模结果：
-7÷(-2)=4…… 1 (Ⅵ) → 4×(-2)+1=-7
-7÷(-2)=3……-1 (Ⅹ) → 3×(-2)-1=-7观察得知，($Ⅵ$)中的商比($Ⅹ$)的多$1$，而余数相差了$abs(R)=2$。
用代数式表达以上观察结果，即
$∵n÷R=x \cdots \cdots p=(x-1) \cdots \cdots q$
$∴n=x×R+p=(x-1)×R+q=x×R+(q-R)$
$∴q-R=p$
事实上，查阅C++11标准$5.6-4$对「取模」的表述（参见Stackoverflow），我们有：
... For integral operands the $/$ operator yields the algebraic quotient with any fractional part discarded; if the quotient $a/b$ is representable in the type of the result, $(a/b)*b + a\%b$ is equal to a.
即：①整数除法$a/b$的结果把小数部分舍弃；②如果$a/b$可表达，那么$(a/b)*b + a\%b = a$.
根据以上规则，有如下推论：
如果$a>0$，则$a\%b=a-(a/b)*b \ge a-a=0$；
如果$a<0$，则$a\%b=a-(a/b)*b \le a-a=0$.
综上，$a\%b$总是与$a$同号，或值为$0$。因此，C++11标准下，被取模数为负数时，结果必非正。
于是，我们只需要在取模结果为负的时候加入一次特判，使之转化成余数为正的情况。
全步骤为：
- 将十进制数$n$对$R$求模，存储余数
- 对$n$进行整数除法$n÷R$
- 【特判】若余数为负，则对余数：$+=abs(R)$；对商：$+1$
- 循环以上过程，直到$n$的值为$0$
- 倒序输出所有余数
Q3: 一点小把戏：处理基数大于$10$时的输出
我们用一维int数组$a[i]$存储第$i$个余数，当$a[i] \ge 10$时，只需按如下方式输出：
printf("%c",a[i]-10+'A');完整代码
#define abs(x) (x>0?x:-x)
#include<cstdio>
int num[200];
int n,r,cnt=-1;
int main()
{
scanf("%d%d",&n,&r);
printf("%d=",n);
while(abs(n)>0) //写n!=0也行（？）
{
if(n%r<0)
{
num[++cnt]=n%r+abs(r);
n/=r;
n++;
continue;
}
num[++cnt]=n%r;
n/=r;
}
for(int i=cnt;i>=0;i--)
{
if(num[i]>9) printf("%c",num[i]-10+'A');
else printf("%d",num[i]);
}
printf("(base%d)",r);
return 0;
}