机试真题3 进制转换2 高精度除法

题目链接

解题思路
这题还是通过高精度的除法来做，思路与上一篇文章类似，区别就是输入输出的进制位数不是固定的。对于输入的进制m，在divide函数中更新余数的时候乘以的数字改成m；对于输出的进制n，在divide函数中取余的分母设置成b。
需要特判的是当输入的字符串为0时，需要直接返回0值。假如不这么做，会导致循环不执行，导致没有任何输出。

参考代码

#include
using namespace std;

int m, n;
vector<int> divide(vector<int> num, int b, int& r)
{
	//此时的num是逆序的
	vector<int> C;  //存储大整数除以b后的数字
	for (int i = num.size() - 1; i >= 0; i--)
	{
		r = r * m + num[i];
		C.emplace_back(r / b);
		r = r % b;
	}
	reverse(C.begin(), C.end());
	while (C.size() > 1 && C.back() == 0) C.pop_back();  //去除后置对于的0
	return C;
}

int main()
{
	ios::sync_with_stdio(false);
	string x;
	cin >> m >> n >> x;
	if (x == "0")  //特判数字为0
	{
		cout << 0;
		return 0;
	}

	vector<int> num;  //存储原始字符串的数值数组
	for (int i = 0; i < x.size(); i++)
	{
		//emplace_back和push_back的最终效果一致，但速度更快
		if (isalpha(x[i])) num.emplace_back(x[i] - 'A' + 10);   //若该字符是字母类型
		else num.emplace_back(x[i] - '0');  //若该字符是数字类型
	}
	reverse(num.begin(), num.end());  //使得数值数组倒序，方便后续存储和操作

	vector<int> ans; //存储每次输出的余数
	while (!(num.size() == 1 && num[0] == 0))  //直到num变为0才退出循环
	{
		int r = 0;  //初始化余数r，作为引用直接传入divide函数
		num = divide(num, n, r);  //取得余数后，更新num
		ans.emplace_back(r);
	}

	reverse(ans.begin(), ans.end());  //余数需要倒置输出
	for (int i = 0; i < ans.size(); i++)
	{
		if (num[i] < 10) cout << num[i];
		else cout << char('a' + num[i] - 10);
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56