ACwing 124. 数的进制转换进制转化

编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。

这里有62个不同数位{0-9,A-Z,a-z}。
输入格式

第一行输入一个整数，代表接下来的行数。

接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。

输入进制和输出进制都在2到62的范围之内。

（在十进制下）A = 10，B = 11，…，Z = 35，a = 36，b = 37，…，z = 61 (0-9仍然表示0-9)。
输出格式

对于每一组进制转换，程序的输出都由三行构成。

第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。

第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。

第三行为空白行。

同一行内数字用空格隔开。
输入样例：

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

输出样例：

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

先推荐y总视频讲解:https://www.acwing.com/video/121/

进制转化方法

把4进制的123转化成5进制的数ans

$(123)_{4} = (102)_{5}$

我们模拟4进制竖式除法

过程如下

第一次 : $123 \div 5 = 011......2 (余 2)$
第二次 : $011 \div 5 = 01.......0 (余 0)$
第三次 : $01 \div 5 = 0........1 (余 1) 直到商 0 为止$
当商为0时,逆回去102就是答案即为 $(102)_{5}$
第一步的运算过程图

第二步运算过程图

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;

string num_parse(int a, int b, string& aline) { //把a进制的str转成b进制的str
	vector<int> num;
	string bline;
	for(auto c : aline) {
		if(c >= '0' && c<='9') num.push_back(c - '0');
		else if(c >= 'A' && c <= 'Z') num.push_back(c - 'A' + 10);
		else if(c >= 'a' && c <= 'z') num.push_back(c - 'a' + 36);
	}
	std::reverse(num.begin(), num.end());

	vector<int> res;
	while(num.size()) { //当商为不为0时就循环
		int r = 0; //r是余数
		for(int i=num.size()-1; i>=0; i--) { //模拟b进制除法
			num[i] += r * a;
			r = num[i] % b;
			num[i] /= b;
		}
		res.push_back(r);
		while(num.size() && num.back()==0) num.pop_back();
	}
	for(auto c : res) {
		if(c <= 9) bline += char(c+'0');
		else if(c >= 10 && c <= 35) bline += char(c+'A'-10);
		else if(c >= 36 && c <= 61) bline += char(c+'a'-36);
	}
	reverse(bline.begin(), bline.end());
	return bline;
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	cin >> Q;
	while(Q--) {
		//把 a 进制的str 转化成 b 进制的str
		int a, b;
		string aline, bline;
		cin >> a >> b >> aline;
#if 0
		vector<int> num;
		for(auto c : aline) {
			if(c >= '0' && c<='9') num.push_back(c - '0');
			else if(c >= 'A' && c <= 'Z') num.push_back(c - 'A' + 10);
			else if(c >= 'a' && c <= 'z') num.push_back(c - 'a' + 36);
		}
		std::reverse(num.begin(), num.end());
		
		vector<int> res;
		while(num.size()) {
			int r = 0;
			for(int i=num.size()-1; i>=0; i--) {
				num[i] += r * a;
				r = num[i] % b;
				num[i] /= b;
			}
			res.push_back(r);
			while(num.size() && num.back()==0) num.pop_back();
		}
		for(auto c : res) {
			if(c <= 9) bline += char(c+'0');
			else if(c >= 10 && c <= 35) bline += char(c+'A'-10);
			else if(c >= 36 && c <= 61) bline += char(c+'a'-36);
		}
		reverse(bline.begin(), bline.end());
#endif
		bline = num_parse(a, b, aline);
		cout << a << " " << aline << endl << b << " " << bline << endl;
		cout << endl;
	}





#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}