$\it{***高精度运算+M进制转N进制***}$
思路:
用字符串读取数字
,然后将读取数字的每一位存到vector数组
中,利用循环进行短除法
操作,将每次短除后的余数存到另一个vector数组中,当第一个vector数组元素变为全0时说明短除彻底退出循环,最后将第二个vector容器里的余数反转后,按位转换成10进制数或字母存放到结果字符串中
要点:
1.字符与数字的转换
,注意与ASCII码的关系
2.短除法(M->N)中,当前位借位与上一位借位的关系:present=(pre*M+res[i])%N
$\quad$pre=present
代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int M,N;
cin>>M>>N;
string str;
//读取第一行残余空格
getchar();
getline(cin,str,'\n');
//res存储源数(每位字母转成10进制),Res存储短除法后的数(余数拼接)
vector<int> res,Res;
//将源数的每一位转换成10进制并按位存在数组中
for(auto c:str)
{
if(c>='0'&&c<='9') res.push_back(c-48);
else if(c>='A'&&c<='Z') res.push_back(c-65+10);
}
//翻转 高位索引存高位数据
reverse(res.begin(),res.end());
//M->N(短除法除N)
//标志数组内元素不全为0
bool flag=0;
do
{
int pre=0,present=0;
for(int i=res.size()-1;i>=0;i--)
{
present=(pre*M+res[i])%N;
//除到最低位,余数添加进结果数组
if(!i) Res.push_back(present);
res[i]=(pre*M+res[i])/N;
pre=present;
}
//判断短除一次后数组表示的数是否全为0
flag=1;
for(auto c:res)
if(c) flag=0;
}while(!flag);
//翻转Res数组,因为短除法得到的结果是余数反向拼接的
reverse(Res.begin(),Res.end());
//将进制转换后的数存入字符串,每位大于10的数转换成字母
string output;
for(int i=0;i<Res.size();i++)
{
if(Res[i]>=10)
{
char c=Res[i]+97-10;
output+=c;
}
else
{
char c=Res[i]+48;
output+=c;
}
}
//输出结果
for(auto c:output)
cout<<c;
return 0;
}
优化(套用高精度除法模板
):只用一位记录余数
//M->N(短除法除N)
while(res.size())
{
//记录余数
int r=0;
for(int i=res.size()-1;i>=0;i--)
{
r=r*M+res[i];
res[i]=r/N;
r%=N;
}
//删除高位0
while(res.size()&&!res.back()) res.pop_back();
Res.push_back(r);
}