P1017 [NOIP2000 提高组] 进制转换 题解

题目简述

给定一个十进制数 $n$，将其转换成一个 $-R$ 进制数。

题目分析

十进制数转负进制，同样可以使用短除取余法，但是会出现余数为负的情况，例如 $-11 \div -2 = 5 ~\cdots \cdots -1$，此时我们可以用如下法方解决此问题：

我们设被除数为 $a$，除数为 $b$，余数为 $c$，商为 $d$，其中 $c<0$ 且 $b<0$。

由除法的定义可知 $a=b \times d +c$，所以有 $a=b \times (d+1)+c-b$，由于余数小于被除数，所以有 $c \lt b$，又因为 $c<0$ 且 $b<0$，所以新的余数 $c-b > 0$。

所以我们只需要将商加 $1$，余数减除数，即可解决余数为负的情况。

代码

#include<iostream>
#include<stack>
using namespace std;
int n,R;
stack<char> s;
int main()
{
	cin>>n>>R;
	cout<<n<<"=";
	while(n)
	{
		int yu=n%R;
		n/=R;
		if(yu<0) n++,yu-=R;
		s.push(char(yu>9?yu+55:yu+'0'));
	}
	while(!s.empty())
	{
		cout<<s.top();
		s.pop();
	}
	cout<<"(base"<<R<<")";
	return 0;
}