自动搬运

查看原文

来自洛谷，原作者为

	forever_nope 原名 RainPPR（好想改回去qwq） | nekoress Rain | 次掉我哦！！1 | AFOed

搬运于2025-08-24 22:58:10，当前版本为作者最后更新于2024-05-24 11:27:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

任意进制转化为十进制

简单的，

$$(\alpha_1\alpha_2\cdots\alpha_n)_k=\sum_{i=1}^n\alpha_ik^{n-i} $$

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

• 顺序考虑原数每一位，记前 $i$ 位答案位 $e_i$，
• $e_i=ke_{i-1}+\alpha_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;
}