【C++】常见高精度计算模板

最近打算新开一个系列，由于博主的记忆力无限趋近于0，学过的基本是秒忘记。因此想到利用自己的博客给自己记录一下代码的模板，方便自己日后的查找使用。

由于博主大脑是混沌体系，所以就没有前后顺序了，想到啥就放上来啥。

最近遇到很多很多很多高精度计算的问题，虽然python一行解决，但是.....

大部分竞赛用不了python😅（虽然但是jvav其实也有高精，但是博主只会Hello World）

（由于禁止复制的策略，你可以点击在新标签页查看再复制!!!）

加法

纯模拟 时间复杂度O(n)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string sum(string& a, string& b)
{
	vector<int> res(202, 0);
	int pos = 0;
	for (int i = a.size() - 1; i >= 0; i--)
	{
		res[pos++] = a[i] - '0';
	}
	for (int i = b.size() - 1; i >= 0; i--)
	{
		res[b.size() - 1 - i] += b[i] - '0';
		res[b.size() - i] += res[b.size() - 1 - i] / 10;
		res[b.size() - 1 - i] %= 10;
	}
	bool f = 0;
	string ans = "";
	for (int i = 201; i >= 0; i--)
	{
		if (res[i] != 0)
		{
			f = 1;
		}
		if (f) ans += res[i] + '0';
	}
	return ans == "" ? "0" : ans;
}

int main()
{
	string a, b;
	cin >> a >> b;
	cout << sum(a, b) << endl;
	return 0;
}

减法

纯模拟 时间复杂度O(n)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string sub(string a, string b)
{
	auto apos = a.find_first_not_of('0');
	auto bpos = b.find_first_not_of('0');
	if (apos != string::npos) a = a.substr(apos);
	if (bpos != string::npos) b = b.substr(bpos);
	bool mark = 0, f = 0;
	int pos = 0;
	vector<int> res(100, 0);
	if (a.size() < b.size() || a < b)
	{
		mark = 1;
		swap(a, b);
	}
	for (int i = a.size() - 1; i >= 0; i--)
	{
		res[pos++] += a[i] - '0';
	}
	for (int i = b.size() - 1; i >= 0; i--)
	{
		if (res[b.size() - 1 - i] - (b[i] - '0') < 0)
		{
			res[b.size() - 1 - i] += 10;
			res[b.size() - i] -= 1;
		}
		res[b.size() - 1 - i] -= b[i] - '0';
	}
	for (int i = b.size(); i <= 81; i++)
	{
		if (res[i] < 0)
		{
			res[i] += 10;
			res[i + 1] -= 1;
		}
	}
	string ans = mark ? "-" : "";
	for (int i = 81; i >= 0; i--)
	{
		if (res[i] != 0)
		{
			f = 1;
		}
		if (f) ans += res[i] + '0';
	}
	return (ans == "" || ans == "-") ? "0" : ans;
}

int main()
{
	string a, b;
	cin >> a >> b;
	cout << sub(a, b) << endl;
	return 0;
}

乘法

分为低精度×高精度和高精度×高精度两个版本。

(由于博主很笨，压位高精还没学会，这里没有提供。如果以后学会会补充上的...)

高精度×低精度

纯模拟 时间复杂度O(n)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

string mul(string a, int b)
{
	vector<int> tmp, res(202, 0);
	for (int i = a.size() - 1; i >= 0; i--)
	{
		tmp.emplace_back(a[i] - '0');
	}
	for (int i = 0; i < tmp.size(); i++)
	{
		res[i] += tmp[i] * b;
		res[i + 1] += res[i] / 10;
		res[i] %= 10;
	}
	for (int i = tmp.size(); i <= 200; i++)
	{
		res[i + 1] += res[i] / 10;
		res[i] %= 10;
	}
	bool f = 0;
	string ans = "";
	for (int i = 200; i >= 0; i--)
	{
		if (res[i] != 0) f = 1;
		if (f)
		{
			ans += res[i] + '0';
		}
	}
	return ans == "" ? "0" : ans;
}

int main()
{
	string a;
	int b;
	cin >> a >> b;
	cout << mul(a, b) << endl;
	return 0;
}

高精度×高精度

抄袭模板 时间复杂度O(n²)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string multi(string& a, string& b)
{
	vector<int> na(201), nb(201), res(202, 0);
	bool f = 0;
	for (int i = a.size() - 1; i >= 0; i--)
	{
		na[a.size() - 1 - i] = a[i] - '0';
	}
	for (int i = b.size() - 1; i >= 0; i--)
	{
		nb[b.size() - 1 - i] = b[i] - '0';
	}
	for (int i = 0; i <= 200; i++)
	{
		for (int j = 0; j <= i; j++) res[i] += na[j] * nb[i - j];
		if (res[i] >= 10)
		{
			res[i + 1] += res[i] / 10;
			res[i] %= 10;
		}
	}
	string ans = "";
	for (int i = 200; i >= 0; i--)
	{
		if (res[i] != 0) f = 1;
		if (f) ans += res[i] + '0';
	}
	return ans == "" ? "0" : ans;
}
int main()
{
	string a, b;
	cin >> a >> b;
	cout << multi(a, b) << endl;
	return 0;
}

除法

和乘法一致，分为高精度÷低精度和高精度÷高精度两个版本。

高精度÷低精度

纯模拟 时间复杂度O(n)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

string div(string& a, int b)
{
	string res = "";
	long long remain = 0;
	for (auto& i : a)
	{
		remain = remain * 10 + i - '0';
		res += remain / b + '0';
		remain %= b;
	}
	auto it = res.find_first_not_of('0');
	if (it != string::npos) return res.substr(it);
	else return "0";
}

int main()
{
	string a;
	int b;
	cin >> a >> b;
	cout << div(a, b) << endl;
	return 0;
}

高精度÷高精度

代码完全抄袭自oi-wiki

高精度快速幂

不知道放哪里。就先放在这里了🤓

代码完全抄袭自oi-wiki

题目：[NOIP 2003 普及组] 麦森数（https://www.luogu.com.cn/problem/P1045）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
vector<int> a(505), b(505), tmp(505);

void multi(vector<int>& x, vector<int>& y)
{
	tmp = vector<int>(505, 0);
	for (int i = 1; i <= x[0]; i++)
	{
		for (int j = 1; j <= y[0]; j++)
		{
			if (i + j - 1 > 500) continue;
			tmp[i + j - 1] += x[i] * y[j];
			tmp[i + j] += tmp[i + j - 1] / 10;
			tmp[i + j - 1] %= 10;
			tmp[0] = i + j;
		}
	}
	b = tmp;
}

// kasumi 也是快速幂
void kasumi(int n)
{
	if (n == 1)
	{
		b = a;
		return;
	}
	kasumi(n / 2);
	multi(b, b);
	if (n % 2 != 0) multi(b, a);
}

int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	int p;
	cin >> p;
	int res = p * log10(2) + 1;
	cout << res;
	a[0] = 1, b[0] = 1;
	a[1] = 2, b[1] = 1;
	kasumi(p);
	for (int i = 500; i >= 1; i--)
	{
		if (i % 50 == 0) cout << endl;
		if (i == 1)
		{
			cout << b[i] - 1 << endl;
			break;
		}
		cout << b[i];
	}
	return 0;
}

目前就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。