进制转换

题目

小f来到了璃月和须弥交接处的层岩巨渊。层岩巨渊是璃月的领土，曾经作为璃月最重要的矿场，有着悠久的历史。但是在近期，这里却因为怪事频发导致大多数工人暂时离开。

在这里，小f遇到了一种奇特的机关。这种机关旁边刻了两个数字 a, b，小f通过询问当地人得知，想要通过这个机关需要将 a 转换为 b 进制数。这可难不倒小f，他十分快速地得到答案，输入了进去，但是机关却发出了刺耳的鸣叫。很显然小f的答案不对，请你帮他得出正确的答案，他会将机关后的珍宝分你一半。

在 16 进制中，我们用 A 表示 10，B 表示 11。以此类推，可知道在 36 进制中 Z 表示 35。

输入：两个十进制数字 a, b。
输出：一个数，表示 a 在 b 进制下的数。
数据范围：1 ≤ a ≤ 10000，1 ≤ b ≤ 36。
注意：处理 0。

样例：

123 25

4N

思路

不断 a % b 取余数、a /= b 更新，余数即为各位数字（低位先出）。用字符串 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 做映射表，余数直接作下标取字符，拼到结果字符串末尾，最后 reverse 反转即为答案。

#include<bits/stdc++.h>
using namespace std;

string convert(int a, int b){
    string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string rever="";
    while(a!=0){
        rever+=digits[a%b];
        a/=b;
    }
    reverse(rever.begin(),rever.end());
    return rever;
}

int main(){
    int a,b;
    cin>>a>>b;
    cout<<convert(a,b)<<endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(log_b a)，循环次数为 a 在 b 进制下的位数。
• 空间复杂度：O(log_b a)，存储结果字符串。

← 返回菜鸟的coding