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

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

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

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

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

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

加法

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

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

using namespace std;
constexpr int MAXN = 1e3;

string sum(string a, string b)
{
	if (a.size() > b.size() || (a.size() == b.size() && a > b)) swap(a, b);
	vector<int> res(MAXN + 3, 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 = MAXN; 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;
constexpr int MAXN = 1e3;

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(1e3 + 5, 0);
    if (a.size() < b.size() || (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 <= MAXN; i++)
    {
        if (res[i] < 0)
        {
            res[i] += 10;
            res[i + 1] -= 1;
        }
    }
    string ans = mark ? "-" : "";
    for (int i = MAXN; 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> res(a.size() + 10, 0);
	for (int i = a.size() - 1; i >= 0; i--)
	{
		res[a.size() - i - 1] = (a[i] - '0') * b;
	}
	for (int i = 0; i < res.size(); i++)
	{
		if (res[i] >= 10)
		{
			res[i + 1] += res[i] / 10;
			res[i] %= 10;
		}
	}
	while (res.size() > 1 && res.back() == 0)
	{
		res.pop_back();
	}
	string ans = "";
	for (int i = res.size() - 1; i >= 0; i--)
	{
		ans += res[i] + '0';
	}
	return 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;
constexpr int MAXN = 1e3;

string multi(string& a, string& b)
{
	vector<int> na(MAXN + 3), nb(MAXN + 3), res(MAXN + 5, 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 <= MAXN; 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 = MAXN; 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。时间复杂度为O(n^2)

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

using namespace std;
constexpr int MAXN = 1e3;

bool candiv(vector<int>& a, vector<int>& b, int apos, int blen)
{
	if (a[apos + blen] != 0) return 1;
	for (int i = blen - 1; i >= 0; i--)
	{
		if (a[apos + i] > b[i]) return 1;
		if (a[apos + i] < b[i]) return 0;
	}
	return 1;
}

string div(string& x, string& y)
{
	if (y == "0") return "-1";
	if (y == "1") return x;
	vector<int> a(MAXN + 5), b(MAXN + 5), res(MAXN + 5);
	for (int i = x.size() - 1; i >= 0; i--) a[x.size() - 1 - i] = x[i] - '0';
	for (int i = y.size() - 1; i >= 0; i--) b[y.size() - 1 - i] = y[i] - '0';
	int len = x.size() - y.size();
	for (int i = x.size() - y.size(); i >= 0; i--)
	{
		while (candiv(a, b, i, y.size()))
		{
			res[i]++;
			for (int j = 0; j < y.size(); j++)
			{
				if (a[i + j] < b[j])
				{
					a[i + j + 1]--;
					a[i + j] += 10;
				}
				a[i + j] -= b[j];
			}
		}
	}
	string ans = "";
	bool f = 0;
	for (int i = MAXN; i >= 0; i--)
	{
		if (res[i] != 0) f = 1;
		if (f) ans += res[i] + '0';
	}
	return ans;
}

int main()
{
	string a, b;
	cin >> a >> b;
	if (a.size() < b.size() || (a.size() == b.size() && a < b))
	{
		cout << "0" << endl;
		return 0;
	}
	cout << div(a, b) << endl;
	return 0;
}

高精度快速幂

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

代码完全抄袭自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;
}

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