高精度运算

先将n进制转换为10进制，再讲10进制转换为m进制，由于中间结果可能很大，需要用到高精度运算

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int input, output;
string s;

//得到字符对应的十进制数
int get(char ch){
    if(isdigit(ch)) return ch - '0';
    if(islower(ch)) return ch - 'a' + 36;
    return ch - 'A' + 10;
}

//得到十进制数对应的字符
char get_ch(int digit){
    if(digit >= 0 && digit <= 9) return digit + '0';
    else if(digit >= 10 && digit <= 35) return digit - 10 + 'A';
    else return digit - 36 + 'a';
}

//高精度加法
vector<int> add(vector<int> a, vector<int> b){
    if(a.size() < b.size()) return add(b, a);
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size(); i++){
        t += a[i];
        if(i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
        }
    if(t) c.push_back(t);
    return c;
}

//高精度乘法
void mul(vector<int> &a, int d){
    int t = 0;
    for(int i = 0; i < a.size(); i++){
        a[i] = a[i] * d + t;
        t = a[i] / 10;
        a[i] = a[i] % 10;
        }
    while(t){
        a.push_back(t % 10);
        t /= 10;
        }
    while(a.size() > 1 && a.back() == 0) a.pop_back();
}

vector<int> div(vector<int> &a, int d, int &r){
    vector<int> c;
    r = 0;
    for(int i = a.size() - 1; i >= 0; i--){
        r = r * 10 + a[i];
        c.push_back(r / d);
        r %= d;
        }
    reverse(c.begin(), c.end());
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

//将input进制数转换为10进制数
void toTen(vector<int> &a){
    int exp = 0;
    for(int i = s.size() - 1; i >= 0; i--){
        int digit = get(s[i]);
        vector<int> b;
        while(digit){
            b.push_back(digit % 10);
            digit /= 10;
            }
        for(int j = 0; j < exp; j++){
            mul(b, input);
            }
        a = add(a, b);
        exp++;
        }
}

//将10进制数转换为output进制数
string toNradix(vector<int> &a){
    vector<int> c;
    int r = 0;
    string ans;
    while(a.back() != 0){
        a = div(a, output, r);
        char ch = get_ch(r);
        ans += ch;
        }
    reverse(ans.begin(), ans.end());
    return ans;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        cin >> input >> output >> s;
        vector<int> a;  //存储转换为的十进制数
        a.push_back(0);
        toTen(a);
        string ans = toNradix(a);
        if(s.size() == 1 && s[0] == '0') ans = s;
        cout << input << " " << s << endl;
        cout << output << " " << ans << endl;
        cout << endl;
        }
    return 0;
}