【数论/递归】P1017 进制转换

原题：https://www.luogu.com.cn/problem/P1017

（不再粘贴题目了，太麻烦）

P1017 进制转换 【普及/提高-】 题解

第一部分：痛苦与绝望

经过了两个小时的煎熬，这道题基本可以算是将近把我逼疯了。看着其他同学的五一假期作业分数早已经突破800分，【提高+/省选-】的题一遍就过，我却还在400分左右徘徊，这样一道黄题都过不了......

废话不多说，进入正题

这是我耗了两个小时的成果：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
vector<int> a;
int n,R,len;
pair<int,int> range[100];
char vir[21]="0123456789ABCDEFGHIJ";
int main()
{
    cin>>n>>R;
    range[0].first=0;
    range[0].second=-R;
    for(int i=0; pow(-R,i)<=2147483647; i++)
    {
        if(i%2==1)
        {
            range[i].first=range[i-1].first-pow(-R,i);
            range[i].second=range[i-1].second;
        }
        else if(i%2==0)
        {
            range[i].first=range[i-1].first;
            range[i].second=range[i-1].second+pow(-R,i);
        }
        if(n<=range[i].second&&n>=range[i].first)
        {
            len=i;
            break;
        }
    }
//    cout<<len<<endl;
    cout<<n<<"=";
    for(int i=len+1; i>=1; i--)
    {
        if((i-1)%2==0&&n>0)
        {
            for(int j=0;; j++)
            {
                if(j*pow(-R,i-1)>=n||j==-R-1)
                {
                    //cout<<pow(-R,i-1)<<endl<<n<<endl;
                    cout<<vir[j];
                    n -= j*pow(-R,i-1);
                    break;
                }
            }
        }
        else if((i-1)%2==1&&n<0)
        {
            for(int j=0;; j++)
            {
                if(-(j)*pow(-R,i-1)<=n||j==-R-1)
                {
                //    cout<<-pow(-R,i-1)<<endl<<n<<endl;
                    cout<<vir[j];
                    n += j*pow(-R,i-1);
                    break;
                }
            }
        }
        else
        {
            cout<<0;
            continue;
        }
    }
    cout<<"(base"<<R<<")"<<endl;
    return 0;
}

然而命运多舛，如果给定的数是负数，这个代码就无能为力了。我将近哭了出来，心想难道这就是智力不够吗......就是因为它，还有其他同学遥遥领先的进度，我在网课上将近崩溃，不得不请假离开......

第二部分：清醒与悔悟

痛定思痛，结合题解，我认真地反思了一下。

把十进制转换成其他进制，最基础的方法是什么？

不就是用原十进制数一步步除以要转换的进制数，将余数倒序输出么！这题虽然有负数，但思路一定是同样的，只需要做出一些微调就行！

然而，从一开始，我的思路就错了。我先从“大”处理，就是先算出转换后的位数，然后一步步调用pow（求幂函数），一开始就会出现很大的数字，然后再求值、取余......殊不知这已经远远偏离了正确思路。

在数次痛苦的哀嚎后，我才明白，这是无济于事的。我需要解决问题。

经过一次次心理的狂风巨浪以后，我的思路正在向真理接近......

第三部分：希望与涅槃

以下是正确的思路。

对于非负数进制的转换（原数是十进制），设要转换成 R 进制，只要每次将原数除以 R ，得到一系列余数 m₁ , m₂ , m₃ ... m_n ，然后再按照逆着的顺序输出 m_{n ,}m_n-1 , ... , m₃ , m₂ ,  m_1。

也就是说，我们只需要取余，从原数减去 余数乘以进制数 R 的积 ，然后继续往下寻找（递归）就行。

//版本1
void turn(int n,int r)//n是当前需要模的数字，r是模数
{
    if(n==0) return;
    int m=n%r;
    存储m;
    turn(n/r,r);//下一步
}
int main()
{
    输入n,r;
    turn(n,r);
    倒序输出所有存储的m;
}
//版本2
void turn(int n,int r)
{
    if(n==0)return;
    int m=n%r;
    turn(n/r,r);
    cout<<m;//在递归后输出，能保证倒序
}

但是对于这道题，很明显其中会出现负数。对于被模数是负数的情况，计算机会返回一个负数，例如：-5 % -3 = -2 , -5 % 3 = -2。

负数余数是我们不想要的情况，需要把它转换成正数。

经过很长时间的探究后，我发现了规律：如果出现负数余数，那么就把它减去负进制数 R （R < 0），这样会使它成为正数，然后进行下一步递归时，将 n 除以 r 所得的商加上 1 ：

m-=r;
turn(n/r+1,r);

然后再根据正数情况处理就行了。

我的代码运用STL模板，具有很高的整合性。我的想法：单独地编写一个取余函数，能够处理负数余数。然后返回一个pair，一个存储得到的余数，一个存储一个bool值，表示它是不是遇到了负数的情况，也就是商需不需要加一。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
char vir[21]="0123456789ABCDEFGHIJ";
int N,R;
stack<int> st;//栈具有后进先出的性质，适合倒序输出 
pair<int,bool> ultra_mod(int n,int r)
{
    int mod=n%r;
    pair<int,bool> res;
    if(mod<0)
    {
        mod-=r;//处理负余数 
        res.second=true;//有负余数，需要在下一步递归时+1 
    } 
    else res.second=false;//不需要+1 
    res.first=mod;//导出余数 
    return res;
}
void turn(int n,int r)
{
    if(n==0) return;//停止递归 
    pair<int,bool> mod=ultra_mod(n,r);//获得余数信息 
    st.push(mod.first);//将余数压进栈 
    if(mod.second == true) turn(n/r+1,r);//遇到负数情况 
    else turn(n/r,r);
}
int main()
{
    cin>>N>>R;
    turn(N,R);
    cout<<N<<"=";
    while(!st.empty())
    {
        cout<<vir[st.top()];//倒序输出所有余数（若大于9先转换成字母） 
        st.pop();
    }
    cout<<"(base"<<R<<")";
    return 0;
}