高精度模板

这是我~~因为一个小错调了一中午~~苦苦钻研凝结出的精华，请放心食用
本博客涉及高精度加、减、乘、除、取余

定义&初始化

定义

struct bn {
	ll num[N] = {0};
	int len = 1, fu = 0;
	void init_num (ll x);
	void init_s (string s);
};

两种初始化

//用整形初始化
void bn :: init_num (ll x) {
	len = 0;
	fu = x < 0 ? 1 : 0;
	while (x) {
		num[++len] = x % 10;
		x /= 10;
	}
}
//用字符串初始化
void bn :: init_s (string s) {
	int siz = s.size ();
	if (s[0] == '-') {
		fu = 1;
		for (int i = 1; i < siz; i++) 
			num[siz - i] = s[i] - '0';
		len = siz - 1;
	} else {
		fu = 0;
		for (int i = 0; i < siz; i++) {
			num[siz - i] = s[i] - '0';
		}
		len = siz;
	}
}

输出

void prt (bn a) {
	if (a.fu) printf ("-");
	for (int i = a.len; i >= 1; i--) 
		printf ("%lld", a.num[i]);
	printf("\n");
}

两个比较函数

//这个直接比较
int cmp (bn a, bn b) {
//a > b return 1;
//a < b return -1;
//a == b return 0;
	if (!a.fu && b.fu) return 1;
	if (a.fu && !b.fu) return -1;
	if (!a.fu && !b.fu) {
		if (a.len > b.len) return 1;
		if (a.len < b.len) return -1;
		for (int i = a.len; i >= 1; i--) {
			if (a.num[i] > b.num[i]) return 1;
			if (a.num[i] < b.num[i]) return -1;
		}
		return 0;
	}
	if (a.fu && b.fu) {
		if (a.len > b.len) return -1;
		if (a.len < b.len) return 1;
		for (int i = a.len; i >= 1; i--) {
			if (a.num[i] > b.num[i]) return -1;
			if (a.num[i] < b.num[i]) return 1;
		}
		return 0;
	}
}
//这个比较绝对值
int abs_cmp (bn a, bn b) {
	if (a.len > b.len) return 1;
	if (a.len < b.len) return -1;
	for (int i = a.len; i >= 1; i--) {
		if (a.num[i] > b.num[i]) return 1;
		if (a.num[i] < b.num[i]) return -1;
	}
	return 0;
}

高精加/减

bn pls (bn a, bn b) {
	bn res;
	//同号直接加即可
	if ((a.fu && b.fu) || (!a.fu && !b.fu)) {
		int siz = max (a.len, b.len);
		for (int i = 1; i <= siz; i++) {
			res.num[i] += a.num[i] + b.num[i];
			res.num[i + 1] += res.num[i] / 10;
			res.num[i] %= 10;
		}
		if (res.num[siz + 1]) {
			siz++;
			while (res.num[siz] >= 10) {
				res.num[siz + 1] += res.num[siz] / 10;
				res.num[siz] %= 10;
				siz++;
			}
		}
		res.len = siz;
		res.fu = a.fu;
		return res;
	} else {
	//异号变为减
		int cmp_re = abs_cmp (a, b);
		//绝对值大的为被减数，另一个为减数
		if (cmp_re > 0) {
			res.fu = a.fu;
		} else if (cmp_re < 0) {
			res.fu = b.fu;
			swap(a, b);
		} else {
			res.fu = 0;
			res.len = 1;
			return res;
		}
		int siz = a.len;
		for (int i = 1; i <= siz; i++) {
			res.num[i] += a.num[i] - b.num[i];
			if (res.num[i] < 0) {
				res.num[i] += 10;
				res.num[i + 1] -= 1;
			}
		}
		while (res.num[siz] == 0 && siz > 1) siz--;
		res.len = siz;
		return res;
	}
}

高精乘低精

//这里b如果需要到ll, 那么定义的时候也要将num[]定义为ll, 否则会炸
bn mul_l (bn a, ll b) {
	int siz = a.len;
	if (b < 0) a.fu ^= 1, b *= -1;
	//这里注意不能一边乘一边进位，否则同一个数会被乘多次，导致答案错误
	for (int i = 1; i <= a.len; i++)
		a.num[i] *= b;
	for (int i = 1; i <= a.len; i++) {
		a.num[i + 1] += a.num[i] / 10;
		a.num[i] %= 10;
	}
	if (a.num[siz + 1]) {
		siz++;
		while (a.num[siz] >= 10) {
			a.num[siz + 1] += a.num[siz] / 10;
			a.num[siz] %= 10;
			siz++;
		}
	}
	a.len = siz;
	return a;
}

高精乘高精

这里就是模拟手算乘法，注意一下处理前导零

bn mul_h (bn a, bn b) {
	bn res;
	res.fu = a.fu ^ b.fu;
	int siz = a.len + b.len;
	for (int i = 1; i <= a.len; i++)
		for (int j = 1; j <= b.len; j++)
			res.num[i + j - 1] += a.num[i] * b.num[j];
	for (int i = 1; i <= siz; i++) {
		res.num[i + 1] += res.num[i] / 10;
		res.num[i] %= 10;
	}
	if (res.num[siz + 1]) {
		siz++;
		while (res.num[siz] >= 10) {
			res.num[siz + 1] += res.num[siz] / 10;
			res.num[siz] %= 10;
			siz++;
		}
	}
	while (res.num[siz] == 0) siz--;
	res.len = siz;
	return res;
}

高精除低精

bn div_l (bn a, ll b, bool op) {
	bn res;
	ll rem = 0;
	if (b < 0) res.fu = a.fu ^ 1, b *= -1;
	for (int i = a.len; i >= 1; i--) {
		rem = rem * 10 + a.num[i];
		if (rem >= b) {
			res.num[i] = rem / b;
			rem = rem % b;
		} else res.num[i] = 0;
	}
	if (op == 0) {
		res.init_num (rem);
		return res;
	}
	res.len = a.len;
	while (res.num[res.len] == 0) res.len--;
	return res;
}

高精除高精

bn div_h (bn a, bn b, bool op) {
	bn res;
	if (abs_cmp (a, b) < 0) {
		if (op == 0) return a;
		else return res;
	}
	res.fu = a.fu ^ b.fu;
	int fua = a.fu;
	b.fu = 0, a.fu = 0;
	
	int t = a.len - b.len;
	
	for (int i = a.len; i >= 1; i--) {
		if (i > t) {
			b.num[i] = b.num[i - t];
		} else b.num[i] = 0;
	}
	b.len = a.len;
	for (int i = 0; i <= t; i++) {
		while (cmp (a, b) >= 0) {
			res.num[t + 1 - i] ++;
			b.fu = 1;
			a = pls (a, b);
			b.fu = 0;
		}
		for (int j = 1; j <= b.len; j++) {
			b.num[j] = b.num[j + 1];
		}
		b.num[b.len] = 0;
		b.len--;
	}
	
	for (int i = 1; i <= t + 1; i++) {
		if (res.num[i]) {
			res.len = i;
			res.num[i + 1] += res.num[i] / 10;
			res.num[i] %= 10;
		}
	}
	if (op == 0) {
		a.fu = fua;
		return a;
	}
	return res;
}

大礼包例题

传送门

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 2e4 + 10;

struct bn {
	ll num[N] = {0};
	int len = 1, fu = 0;
	void init_num (ll x);
	void init_s (string s);
};

void prt (bn a);
int cmp (bn a, bn b);
int abs_cmp (bn a, bn b);
bn pls (bn a, bn b);
bn mul_l (bn a, ll b);
bn mul_h (bn a, bn b);
bn div_l (bn a, ll b, bool op);
bn div_h (bn a, bn b, bool op);

int main () {
	string s1, s2;
	bn a, b, c;
//	ll tt;
	cin >> s1 >> s2;
	a.init_s (s1);
	b.init_s (s2);
//	prt (a), prt (b);
	c = pls (a, b); prt (c);
	b.fu ^= 1;
	c = pls (a, b); prt (c);
	b.fu ^= 1;
	c = mul_h (a, b); prt (c);
	c = div_h (a, b, 1); prt (c);
	c = div_h (a, b, 0); prt (c);
	
	return 0;
}

void bn :: init_num (ll x) {
	len = 0;
	fu = x < 0 ? 1 : 0;
	while (x) {
		num[++len] = x % 10;
		x /= 10;
	}
}

void bn :: init_s (string s) {
	int siz = s.size ();
	if (s[0] == '-') {
		fu = 1;
		for (int i = 1; i < siz; i++) 
			num[siz - i] = s[i] - '0';
		len = siz - 1;
	} else {
		fu = 0;
		for (int i = 0; i < siz; i++) {
			num[siz - i] = s[i] - '0';
		}
		len = siz;
	}
}

void prt (bn a) {
	if (a.fu) printf ("-");
	for (int i = a.len; i >= 1; i--) 
		printf ("%lld", a.num[i]);
	printf("\n");
}

int cmp (bn a, bn b) {
//a > b return 1;
//a < b return -1;
//a == b return 0;
	if (!a.fu && b.fu) return 1;
	if (a.fu && !b.fu) return -1;
	if (!a.fu && !b.fu) {
		if (a.len > b.len) return 1;
		if (a.len < b.len) return -1;
		for (int i = a.len; i >= 1; i--) {
			if (a.num[i] > b.num[i]) return 1;
			if (a.num[i] < b.num[i]) return -1;
		}
		return 0;
	}
	if (a.fu && b.fu) {
		if (a.len > b.len) return -1;
		if (a.len < b.len) return 1;
		for (int i = a.len; i >= 1; i--) {
			if (a.num[i] > b.num[i]) return -1;
			if (a.num[i] < b.num[i]) return 1;
		}
		return 0;
	}
}

int abs_cmp (bn a, bn b) {
	if (a.len > b.len) return 1;
	if (a.len < b.len) return -1;
	for (int i = a.len; i >= 1; i--) {
		if (a.num[i] > b.num[i]) return 1;
		if (a.num[i] < b.num[i]) return -1;
	}
	return 0;
}

bn pls (bn a, bn b) {
	bn res;
	if ((a.fu && b.fu) || (!a.fu && !b.fu)) {
		int siz = max (a.len, b.len);
		for (int i = 1; i <= siz; i++) {
			res.num[i] += a.num[i] + b.num[i];
			res.num[i + 1] += res.num[i] / 10;
			res.num[i] %= 10;
		}
		if (res.num[siz + 1]) {
			siz++;
			while (res.num[siz] >= 10) {
				res.num[siz + 1] += res.num[siz] / 10;
				res.num[siz] %= 10;
				siz++;
			}
		}
		res.len = siz;
		res.fu = a.fu;
		return res;
	} else {
		int cmp_re = abs_cmp (a, b);
		if (cmp_re > 0) {
			res.fu = a.fu;
		} else if (cmp_re < 0) {
			res.fu = b.fu;
			swap(a, b);
		} else {
			res.fu = 0;
			res.len = 1;
			return res;
		}
		int siz = a.len;
		for (int i = 1; i <= siz; i++) {
			res.num[i] += a.num[i] - b.num[i];
			if (res.num[i] < 0) {
				res.num[i] += 10;
				res.num[i + 1] -= 1;
			}
		}
		while (res.num[siz] == 0 && siz > 1) siz--;
		res.len = siz;
		return res;
	}
}

bn mul_l (bn a, ll b) {
	int siz = a.len;
	if (b < 0) a.fu ^= 1, b *= -1;
	for (int i = 1; i <= a.len; i++)
		a.num[i] *= b;
	for (int i = 1; i <= a.len; i++) {
		a.num[i + 1] += a.num[i] / 10;
		a.num[i] %= 10;
	}
	if (a.num[siz + 1]) {
		siz++;
		while (a.num[siz] >= 10) {
			a.num[siz + 1] += a.num[siz] / 10;
			a.num[siz] %= 10;
			siz++;
		}
	}
	a.len = siz;
	return a;
}

bn mul_h (bn a, bn b) {
	bn res;
	res.fu = a.fu ^ b.fu;
	int siz = a.len + b.len;
	for (int i = 1; i <= a.len; i++)
		for (int j = 1; j <= b.len; j++)
			res.num[i + j - 1] += a.num[i] * b.num[j];
	for (int i = 1; i <= siz; i++) {
		res.num[i + 1] += res.num[i] / 10;
		res.num[i] %= 10;
	}
	if (res.num[siz + 1]) {
		siz++;
		while (res.num[siz] >= 10) {
			res.num[siz + 1] += res.num[siz] / 10;
			res.num[siz] %= 10;
			siz++;
		}
	}
	while (res.num[siz] == 0) siz--;
	res.len = siz;
	return res;
}

//quotient 商数 op == 1 求商
//remainder 余数 op == 0 求余

bn div_l (bn a, ll b, bool op) {
	bn res;
	ll rem = 0;
	if (b < 0) res.fu = a.fu ^ 1, b *= -1;
	for (int i = a.len; i >= 1; i--) {
		rem = rem * 10 + a.num[i];
		if (rem >= b) {
			res.num[i] = rem / b;
			rem = rem % b;
		} else res.num[i] = 0;
	}
	if (op == 0) {
		res.init_num (rem);
		return res;
	}
	res.len = a.len;
	while (res.num[res.len] == 0) res.len--;
	return res;
}

bn div_h (bn a, bn b, bool op) {
	bn res;
	if (abs_cmp (a, b) < 0) {
		if (op == 0) return a;
		else return res;
	}
	res.fu = a.fu ^ b.fu;
	int fua = a.fu;
	b.fu = 0, a.fu = 0;
	
	int t = a.len - b.len;
	
	for (int i = a.len; i >= 1; i--) {
		if (i > t) {
			b.num[i] = b.num[i - t];
		} else b.num[i] = 0;
	}
	b.len = a.len;
	for (int i = 0; i <= t; i++) {
		while (cmp (a, b) >= 0) {
			res.num[t + 1 - i] ++;
			b.fu = 1;
			a = pls (a, b);
			b.fu = 0;
		}
		for (int j = 1; j <= b.len; j++) {
			b.num[j] = b.num[j + 1];
		}
		b.num[b.len] = 0;
		b.len--;
	}
	
	for (int i = 1; i <= t + 1; i++) {
		if (res.num[i]) {
			res.len = i;
			res.num[i + 1] += res.num[i] / 10;
			res.num[i] %= 10;
		}
	}
	if (op == 0) {
		a.fu = fua;
		return a;
	}
	return res;
}

Menu

Share

定义&初始化

定义

两种初始化

输出

两个比较函数

高精加/减

高精乘低精

高精乘高精

高精除低精

高精除高精

大礼包例题

Comment

数论学习笔记

16 ABC404 A ~ E 题解

模拟赛T2 hack

【模板】树链剖分

模拟赛T4 题解

4.23模拟赛总结

高精度模板

（勿入）帮一个大学生通过小测

梅深不见冬题解

2025 04 30 模拟赛题解