题解：P10462 Number Base Conversion

forever_nope · 2024-05-24 11:27:45 · 题解

进制转换板子题，下面是前置知识，

任意进制转化为十进制

简单的，

算法实现，即秦九韶算法，

• 顺序考虑原数每一位，记前 i 位答案位 e_i，

十进制转化为任意进制

短除法，

• 原数，不断除以目标进制 k，所得商、余数：
• 商，作为下一轮的被除数，
• 余数，作为结果的一位。

不断进行上述操作，所得结果序列，逆序，即目标数。

任意进制之间的转化

假设我们要把 p 进制数转化为 q 进制数。

于是，我们可以把原数，在 p 进制下除以 q。

不断迭代，类似上面的。

类比十进制下的除法，我们进位的时候需要乘上 p 而不是 10，很显然。

具体做法：

• 原数的每一位，加上上面的进位，除以 q，所得商、余数：
• 商，作为下一轮的被除数的一部分，对于每一位，乘上 p 记为进位。
• 余数：作为结果中的一位。

然后就是模拟了，

#include <bits/stdc++.h>

using namespace std;

int id(char c) {
    if (isdigit(c)) return c - '0';
    if (isupper(c)) return c - 'A' + 10;
    if (islower(c)) return c - 'a' + 10 + 26;
    exit(1);
}

char rnk(int k) {
    if (k < 10) return k + '0';
    if (k < 36) return k - 10 + 'A';
    if (k < 62) return k - 36 + 'a';
    exit(1);
}

void solev() {
    int k1, k2; string s; cin >> k1 >> k2 >> s;
    basic_string<int> n(s.size(), 0), r;
    for (int i = 0; i < s.size(); ++i) n[i] = id(s[i]);
    while (n.size()) {
        basic_string<int> e(n.size(), 0);
        int lt = 0;
        for (int i = 0; i < n.size(); ++i) {
            int c = n[i] + lt * k1;
            e[i] = c / k2, lt = c % k2;
        }
        n = e; r.push_back(lt);
        while (n.size() && n[0] == 0) n.erase(n.begin());
    }
    reverse(r.begin(), r.end());
    cout << k1 << " " << s << endl;
    cout << k2 << " ";
    for (int i : r) cout << rnk(i);
    cout << endl << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T;
    while (T--) solev();
    return 0;
}