[NOIP 2000 提高组] 进制转换

知识点

负进制、除法与余数、数位表示

解题思路

反复求n除以负基数R的商q和余数r。若r<0，将r加|R|，同时q加1，保持n=qR+r不变。记录合法余数作为最低位，最后倒序输出；原数0单独输出0。

正确性说明

修正后余数满足0≤r<|R|且n=qR+r，故当前余数是合法最低位，而剩余高位表示q。反复展开该等式并倒序组合，可还原原整数。数值在有限步内归零，因此得到完整表示。

易错点

原数可能为负或0；基数绝对值可到20，数位超过9用A到J；按样例保留n=表示(baseR)格式。

复杂度

时间O(log(|n|+1))，空间同数位长度。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){long long n;int b;cin>>n>>b;cout<<n<<'=';long long x=n;string s;const string ds="0123456789ABCDEFGHIJ";do{long long r=x%b;x/=b;if(r<0)r-=b,++x;s+=ds[r];}while(x);reverse(s.begin(),s.end());cout<<s<<"(base"<<b<<")\n";}