高精度

2022/8/13 23:28:31

本文主要是介绍高精度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

适用于OI的高精度模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct big{
	typedef pair<big, big> pbb;
	static const int L = 1e3, MOD = 1e4, B = 4;
	ll data[L];
	void clear(){
		 memset(data, 0, sizeof(data));
	}
	big(){
		clear();
	}
	big(const char str[]){
		clear();
		int len = strlen(str + 1);
		data[0] = ceil(1.0 * len / B);
		for(int i = 1; i <= len; ++i){
			int j = ceil (1.0 * (len - i + 1) / B);
			data[j] = data[j] * 10 + str[i] -'0';
		}
		while(data[0] > 1 && !data[data[0]]) --data[0];
	}
	big(ll x){
		clear();
		while(x){
			data[++data[0]] = x % MOD;
			x /= MOD;
		}
		data[0] = max(data[0], 1ll);
	}
	big(int x){
		clear();
		while(x){
			data[++data[0]] = x % MOD;
			x /= MOD;
		}
		data[0] = max(data[0], 1ll);

	}
	big operator =(const big & b){
		memcpy(this, b.data, sizeof(*this));
		return *this;
	}
	friend big operator + (const big& a, const big& b){
		big c;
		c[0] = max(a[0], b[0]);
		for(int i = 1; i <= c[0]; ++i){
			c[i] = a[i] + b[i];
		}
		for(int i = 1; i <= c[0]; ++i){
			c[i + 1] += c[i] / MOD;
			c[i] %= MOD;
		}
		if(c[c[0] + 1]) ++c[0];
		return c;
	}
	friend big operator -(const big& a, const big& b){
		assert(cmp(a, b) != -1);
		big c;
		c[0] = a[0];
		for(int i = 1; i <= a[0]; ++i){
			c[i] = a[i] - b[i];
		}
		for(int i = 1; i <=  a[0]; ++i){
			if(c[i] < 0){
				c[i] += MOD;
				c[i + 1] --;
			}
		}
		while(c[0] > 1 && !c[c[0]]) --c[0];
		return c;
	}
	friend big operator *(const big& a, const big& b){
		big c;
		c[0] = a[0] + b[0] - 1;
		for(int i = 1; i <= a[0]; ++i){
			for(int j = 1; j <= b[0]; ++j){
				c[i + j - 1] += a[i] * b[j];
			}
		}
		for(int i = 1; i <= c[0]; ++i){
			c[i + 1] += c[i] /MOD;
			c[i] %= MOD;
		} 
		if(c[c[0] + 1]) ++c[0];
		return c;
	}
	friend big qpow(big a ,ll k){
		big ret = 1;
		for(;k;k>>=1){
			if(k & 1) ret = ret * a;
			a = a * a;
		}
		return ret;
	}
	friend pbb modres(big a, const big & b){
		big c;
		c[0] = a[0] - b[0] + 1;
		for(int i = c[0] * B; i >= 1; --i){
			big tmp = b * qpow(big(10), i-1);
			int j = ceil(1.0 *i/ B);
			int cnt = 0;
			while(cmp(a, tmp) >= 0) a = a - tmp, ++cnt;
			c[j] = c[j] * 10 + cnt;
		}
		while(c[0] > 1 && !c[c[0]]) --c[0];
		return {c, a};
	}
	friend big operator /(const big& a, const big& b){
		return modres(a, b).first;
	}
	friend big operator %(const big& a, const big& b){
		return modres(a, b).second;
	}
	friend int cmp(const big& a, const big& b){
		if(a[0] != b[0]) return a[0] > b[0] ? 1 : -1;
		for(int i = a[0]; i >= 1; --i){
			if(a[i] != b[i]) return a[i] > b[i] ? 1 : -1;
		}
		return 0;
	}
	ll operator [](int x)const{
		return data[x];
	}
	ll& operator [](int x){
		return data[x];
	}
	string to_str()const{
		stringstream x;
		x << data[data[0]];
		for(int i = data[0] - 1; i >= 1; --i){
			x << setfill('0') << setw(B) << data[i];
		}
		return x.str();
	}
	friend istream& operator >>(istream& in, big& a){
		char tmp[L];
		in >> (tmp + 1);
		a = tmp;
		return in;
	}
	friend ostream& operator <<(ostream& out, big a){
		out << a.to_str();
		return out;
	}
	friend big gcd(big a, big b){
		if(cmp(a, b) == -1) swap(a, b);
		return	cmp(b, 0) == 0? a : gcd(b, a % b);
	}
	friend big sqrt(big a){
		big x = a;
		for(int i = 1; i <= 100; ++i){
			x = (x + a/x) / 2;
		}
		return x;
	}
};
int main(){
	big a, b;
	cin >> a >> b;
	cout << a*b << endl;
	return 0;
}


这篇关于高精度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程