高精度模板

1. 高精度加法

1. 高精度加法其实就是一个模拟过程，模拟我们正常计算。
2. 但是要注意的是，我们正常将两个数进行相加的时候说从右往左进行相加的，所以这里我们的字符串也是要从右往左进行相加的。将相加后的值的个位放到一个vector容器中，并用r记录进位。
3. 就是最后我们的在vector的值是倒着存放的，所以要将其反转后才是正确值。

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>

//高精度加法
int main()
{
	string a, b;
	cin >> a >> b;
	vector<int> ret;

	int i = a.size() - 1, j = b.size() - 1;
	int r = 0;
	while (i >= 0 || j >= 0 || r)
	{
		int sum = 0;
		sum += r;
		if (i >= 0) sum += a[i--] - '0';
		if (j >= 0) sum += b[j--] - '0';
		ret.push_back(sum % 10);
		r = sum / 10;
	}
	reverse(ret.begin(), ret.end());
	for (auto x : ret)
		cout << x;
	return 0;
}

2. 高精度减法

1. 这个其实和高精度加法很相似，就是多了多了一步判断正负数，以及去除前导0的操作
2. 还有就是借位操作

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>

//高精度减法
void sub(string& a, string& b, vector<int>& ret)
{
	int i = a.size() - 1, j = b.size() - 1;
	int r = 0;
	while (i >= 0)
	{
		int sum = a[i--] - '0' + r;
		if (j >= 0)
			sum -= b[j--] - '0';
		ret.push_back((sum + 10) % 10);
		if (sum < 0) r = -1;
		else r = 0;
	}
	//去除前导0
	while (ret.size() > 1 && ret.back() == 0)
		ret.pop_back();
}
int main()
{
	string a, b;
	cin >> a >> b;
	vector<int> ret;

	if (a >= b)
	{
		sub(a, b, ret);
	}
	else
	{
		cout << "-";
		sub(b, a, ret);
	}
	reverse(ret.begin(), ret.end());
	for (auto x : ret)
		cout << x;
	cout << endl;
	return 0;
}

3. 高精度乘法

1. 这里我们采用无进位相乘，这样可以大大减少我们的代码量。
2. 同样的要注意去前导零。

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>

//高精度乘法
int main()
{
	string a, b;
	cin >> a >> b;
	int n = a.size(), m = b.size();
	vector<int> ret(n + m);

	//1.无进位相乘
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			ret[i + j] += (a[i] - '0') * (b[j] - '0');
		}
	}
	//2.处理进位
	int r = 0;
	string tmp;
	for (auto x : ret)
	{
		r += x;
		tmp += r % 10 + '0';
		r /= 10;
	}
	//3. 去除前导零
	while (tmp.size() > 1 && tmp.back() == '0')
		tmp.pop_back();
	reverse(tmp.begin(), tmp.end());
	cout << tmp;	
	return 0;
}

4. 高精度除法

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>

//高精度乘法
int main()
{
	string a;
	int b;
	cin >> a >> b;
	vector<int> ret;

	int num = 0;
	int i = 0;
	while (i < a.size())
	{
		num = num * 10 + a[i++] - '0';
		ret.push_back(num / b);
		num %= b;
	}
	reverse(ret.begin(), ret.end());
	while (ret.size() > 1 && ret.back() == 0)
		ret.pop_back();
	for (int i = ret.size() - 1; i >= 0; i--)
		cout << ret[i];
	cout << endl;
	cout << "余数：" << num;
	return 0;
}