首先想到一种朴素做法就是将读入进来的数转换成十进制,再将其转换成所需进制。
但是C++并不自带高精度,所以我们需要手写高精度。
观察将数转换成所需进制的过程, 发现确定每一位数时只需要得到这个数除以所需进制数的余数即可。
一个数不论以何种进制表示,其除以一个数的余数都是一样的。
所以可以直接将某进制的数除以另一进制的进制数,以此得到余数,构建所需进制的数。
细节不再多说,核心代码在此:
for(int i=len;i>=1;--i)//nxt是所需进制数, pre是原进制数
{
int b=(x*pre+a[i])/nxt;
x=(x*pre+a[i])%nxt;
a[i]=b;
}
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int pre,nxt;
char s[1010011];
int a[1010011];
void work()
{
// string -> number
int len=strlen(s);
for(int i=0;i<len;++i)
{
if(s[i]>='0'&&s[i]<='9') a[len-i]=s[i]-'0';
if(s[i]>='A'&&s[i]<='Z') a[len-i]=s[i]-'A'+10;
if(s[i]>='a'&&s[i]<='z') a[len-i]=s[i]-'a'+36;
}
stack<char>sta;
while(len)
{
int x=0;
for(int i=len;i>=1;--i)//核心代码,高精除低精(除nxt)
{
int b=(x*pre+a[i])/nxt;
x=(x*pre+a[i])%nxt;
a[i]=b;
}
while(!a[len]&&len>=1) --len;
if(x>=0&&x<=9) sta.push((char)(x+'0'));
if(x>=10&&x<=35) sta.push((char)(x-10+'A'));
if(x>=36&&x<=61) sta.push((char)(x-36+'a'));
}
while(!sta.empty()) {
cout<<sta.top();
sta.pop();
}
return;
}
int main()
{
int T; cin >> T;
while(T--)
{
scanf("%d%d%s",&pre,&nxt,s);
printf("%d %s\n",pre,s);
printf("%d ",nxt);
work();
cout<<"\n\n";
}
return 0;
}
牛
佬 是不是一般写高精度直接开静态数组 很少用vector啊
看个人习惯,我就两个都用
膜拜大佬