神秘递归高精度

突发奇想为什么没有__int256，__int114514，然后想能不能直接把64位拼成128，甚至更高。随便实现了一下

实际上就是压位高精度。

并且还不支持动态变化数位长度。

并且还难写，调了一堆bug出来，甚至可能有潜在的bug因为数据太水没测出来，那个高精度A+B问题就5个测试点。

并且还得手动去除前导0。

并且还难读。

并且时空复杂度常数莫名大了很多，因为递归算法，因为递归模板（参见隔壁线段树），因为编译期生成。

CPP

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
int n, m, t, x, y;
template<int Lv>
struct s
{
	static constexpr size_t len = s<Lv - 1>::len << 1;
	s<Lv - 1> a, b;
	pair<bool, s &> ad(const s &o, bool x = 0)
	{
		auto p = a;
		return {a.ad(o.a, b.ad(o.b, x).first).first, *this};
	}
	string &build(string &p)
	{
		b.build(p);
		return a.build(p);
	}
	void get(string &p)
	{
		a.get(p);
		b.get(p);
	}
};

template<>
struct s<0>
{
	static constexpr size_t len = 9;
	unsigned a;
	string &build(string &p)
	{
		if(p.empty())
		{
			a = 0;
			return p;
		}
		a = stoul(p.substr(max(0ll, (lint)p.size() - 9), 9));
		p.resize(max((lint)p.size() - 9, 0ll));
		return p;
	}
	pair<bool, s &> ad(const s &o, bool x = 0)
	{
		unsigned p = a;
		a += o.a + x;
		a %= 1000000000;
		return {p + x > a, *this};
	}
	void get(string &p)
	{
		string s = to_string(a);
		p.append(string(len - s.size(), '0')).append(s);
	}
};
signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	s<6> a, b;
	string q;
	cin >> q;
	a.build(q);
	cin >> q;
	b.build(q);
	a.ad(b);
	q.clear();
	a.get(q);
	int i = 0;
	for(; i < q.size() - 1; i++)
		if(q[i] != '0')
			break;
	cout << q.substr(i, q.size());
}

讨论操作

回复

相关推荐

神秘递归高精度