Yinchuan Regional 2019 I. Base62

Yinchuan Regional 2019
I. Base62
题目链接

---

I. Base62

题意：

把 $x$ 进制数 $z$ 转化为 $y$ 进制数。

思路：

很典型的高精。需要先把 $x$ 进制转化为 $10$ 进制，再把 $10$ 进制转化为 $y$ 进制。

$x\to 10$ 进制的过程是：设置一个高精度 $10$ 进制数 $t$ 用来暂存，每次先给 $t$ 乘以进制 $x$，再取出 $x$ 进制数 $z$ 当前的最高位，然后加入到 $t$，加一遍就是转化后的数。数学证明如下：假设 $z$ 写成 $x$ 进制数的形式为 $a_i{a}_{i-1}\dots a_1{a}_0$
$$\begin{gathered} t(10进制)=z(x进制)=a_i\ast x^i+a_{i-1}\ast x^{i-1}+\cdots +a_1\ast x+a_0(10进制) \\ =((\dots ((a_i\ast x+a_{i-1})\ast x+a_{i-2})\ast x+\dots )\ast x+a_1)\ast x+a_0 \end{gathered}$$照着式子递推即可（其实就是秦九韶算法）。这个过程中需要用到高精加法和乘法。

$10\to y$ 进制的过程是：设置一个高精度 $y$ 进制数 $t$ 用来暂存，然后每次除以 $y$，余数放入 $t$，最后得到的就是 $y$ 进制数了。数学证明如下：假设要转化的 $10$ 进制数写成 $y$ 进制数的形式为 $a_i{a}_{i-1}\dots a_1{a}_0$
$$t(y进制)=((\dots ((a_i\ast y+a_{i-1})\ast y+a_{i-2})\ast y+\dots )\ast y+a_1)\ast y+a_0(10进制)$$观察式子，每次除以 $x$ 的时候，式子总是 $(\dots )\ast y+a_s$ 的形式，余数就是 $a_s$，我们依次除出来的余数就是 $a_0,a_1,a_2,\dots ,a_i$。这个过程需要高精除法，同时需要返回余数。

–分割线–

高精算是典型的比较顶级的模拟题目了，需要注意很多东西。这里强调几点：

1. 一般高精加法和乘法只写高精运算高精，再写个低精转高精的函数就可以不用写高精运算低精的算法了。
2. 高精数最好从低位开始存储，即小下标存放低位数，方便进位（毕竟没有push_front()）。
3. 高精数实现可以使用vector<int>，能实现动态开空间，也方便维护高精数，以下是一些常用用法（假设定义好了一个高精数叫 $a$）：
   1. 返回高精数位数：a.size()
   2. 进位：a.push_back(val)
   3. 去除后导0：while(a.size()>1 && a.back()==0)a.pop_back();（和 reverse(a.begin(),a.end())共同使用可以去除前导0）

code：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int x,y;
string z;
map<char,int> mp1;
map<int,char> mp2;

void print(vector<int> t){
for(auto it=t.rbegin();it!=t.rend();it++)cout<<mp2[*it];
puts("");
return;
}
vector<int> g(int x){
vector<int> a;
do{
a.push_back(x%10);
x/=10;
}while(x);
return a;
}
vector<int> operator+(vector<int> a,vector<int> b){
int n=max(a.size(),b.size());
vector<int> c(n,0);
for(int i=0;i<n;i++)
c[i]=((i<a.size())?a[i]:0)+((i<b.size())?b[i]:0);
int ct=0;
for(int i=0;i<n;i++){
c[i]+=ct;
ct=c[i]/10;
c[i]%=10;
}
while(ct){
c.push_back(ct%10);
ct/=10;
}
return c;
}
vector<int> operator*(vector<int> a,int b){
for(int i=0;i<a.size();i++)
a[i]*=b;
int ct=0;
for(int i=0;i<a.size();i++){
a[i]+=ct;
ct=a[i]/10;
a[i]%=10;
}
while(ct){
a.push_back(ct%10);
ct/=10;
}
return a;
}
pair<vector<int>,int> operator/(vector<int> a,int b){
vector<int> c;
int tmp=0;
for(int i=a.size()-1;i>=0;i--){
tmp*=10;
tmp+=a[i];
c.push_back(tmp/b);
tmp%=b;
}
reverse(c.begin(),c.end());
while(c.size()>1 && c.back()==0)c.pop_back();
return make_pair(c,tmp);
}

vector<int> to10(string s,int p){
vector<int> t(g(0));
for(auto x:s){
t=t*p;
t=t+g(mp1[x]);
}
return t;
}
vector<int> toy(vector<int> t,int y){
vector<int> a;
do{
auto x=t/y;
t=x.first;
a.push_back(x.second);
}while(t!=g(0));
return a;
}

int main(){
for(int i=0;i<=9;i++){
mp1['0'+i]=i;
mp2[i]='0'+i;
}
for(int i=0;i<26;i++){
mp1['A'+i]=10+i;
mp2[10+i]='A'+i;
}
for(int i=0;i<26;i++){
mp1['a'+i]=36+i;
mp2[36+i]='a'+i;
}

cin>>x>>y>>z;

print(toy(to10(z,x),y));

return 0;
}

原文地址：https://blog.csdn.net/qq_45809243/article/details/136149594

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！