I - Base62
题意
给出一个x进制数z<$x^{120}$
输出它的y进制形式
规定’0’-‘9’表示0到9
‘A’-‘Z’表示10到35
‘a’-‘z’表示36到61
题解
参考博客
x进制数z<$x^{120}$ 用字符串读入那么长度不会超过120位
模拟短除法转换进制：
举个例子：50，要从十进制转换为二进制。(即x=10,y=2,z=50)
将十进制每位单独存进数组
十位是5，个位是0，那么首先5/2商为2，余1
下一步就是1*10+0=10，然后个位就变成了10，然后10/2=5余0，
0就是50这个数从十进制转化二进制结果的个位，
然后下一步就是对25进行操作
2/2商1余0，那么十位就是1 个位就是0*10+5=5.
5/2商2余1，那么50的二进制结果的十位就是1。
然后对12进行操作，十位是1，1/2商0余1，那么十位就为0了。
个位就是1*10+2=12.12/2商6余0，结果的百位就是0.
因为十位是0，所以只对个位进行操作了，6/2商3余0，千为就是0
3/2商1余1，万位为1.
1/2商0余1，十万位为1，所以50转换为二进制就是110010
短除法每次对z除以y 大约$log_yz$ 次 每次除法从最高位模拟到最低为最多120位
所以进制转化的复杂度为 $O120log_yz$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e3+5;
const ll Mod=998857459;
int data[200];
map<char,int>alp;
map<int,char>tran;
void intn(){
for(char i='0';i<='9';i++)alp[i]=(i-'0');
for(char i='A';i<='Z';i++)alp[i]=(i-'A'+10);
for(char i='a';i<='z';i++)alp[i]=(i-'a'+36);
char temp='0';
for(int i=0;i<10;i++){
tran[i]=temp;
temp++;
}
temp='A';
for(int i=10;i<36;i++){
tran[i]=temp;
temp++;
}
temp='a';
for(int i=36;i<62;i++){
tran[i]=temp;
temp++;
}
}
char ans[1100];
int main() {
int x,y;
string z,nz="";
cin>>x>>y>>z;
intn();int len=z.size();
for(int i=0;i<len;i++){
data[i]=alp[z[i]];
}
int st=0,indx=0;
while(st<len){
for(int i=st;i<len-1;i++){
data[i+1]+=data[i]%y*x;
data[i]/=y;
}
ans[indx++]=data[len-1]%y;
data[len-1]/=y;
while(st<len&&!data[st])st++;
}
reverse(ans,ans+indx);
for(int i=0;i<indx;i++){
nz+=tran[ans[i]];
}
cout<<nz<<endl;
}
|