首页 > 其他分享 >高精度(有符号)

高精度(有符号)

时间:2023-01-28 16:44:06浏览次数:79  
标签:return val 符号 int big 高精度 base sgn

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct big_base{
	static const int L = 1E4, MOD = 10, B = 1;
	//attention 除法效率 位数^2*MOD 谨慎压位
	//O(n ^2 * (10^B/B^2)) 最优效率为B = 0.75, B = 1即可
	int a[L];
	int& operator [](int x){
		return a[x];
	}
	int operator [](int x)const{
		return a[x];
	}
	big_base(){
		clear();
	}
	void clear(){
		memset(a, 0, sizeof(a));
	}
	big_base (int val) : big_base(to_string(val)) {}
	big_base (ll  val) : big_base(to_string(val)){}
	big_base (string str){
		clear();
		reverse(str.begin(), str.end());
		a[0] = int(str.length() - 1)/ B + 1;
		for(int i = 0, j = 1; i < str.length(); ++i, j *= 10){
			if(j == MOD) j = 1;
			int b = i / B + 1;
			a[b] = (a[b] + (str[i] - '0') * j);
		}
	}
	friend int cmp(const big_base& a, const big_base& b){ // a - 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;
	}
	friend big_base operator +(const big_base&a , const big_base& b){
		big_base c;
		c[0] = max(a[0], b[0]);
		for(int i = 1; i <= c[0]; ++i){
			c[i] += (a[i] + b[i]);
			c[i + 1] += c[i] / MOD;
			c[i] %= MOD;
		}
		if(c[c[0] + 1]) ++c[0];
		return c;
	}
	friend big_base operator - (const big_base& a, const big_base& b){
		big_base c;
		c[0] = a[0];
		for(int i = 1; i <= a[0]; ++i){
			c[i] += a[i] - b[i];
			if(c[i] < 0){
				c[i] += MOD;
				c[i + 1] -= 1;
			}
		}
		while(c[0] > 1 && c[c[0]] == 0) --c[0];
		return c;
	}
	friend big_base operator * (const big_base& a, const big_base& b){
		big_base c;
		c[0] = a[0] + b[0];
		for(int i = 1; i <= a[0]; ++i){
			for(int j = 1; j <= b[0]; ++j){
				c[i + j - 1] += a[i] * b[j];
				c[i + j] += c[i + j - 1] / MOD;
				c[i + j - 1] %= MOD;
			}
		}
		while(c[0] > 1 && c[c[0]] == 0) --c[0];
		return c;
	}
	friend big_base lshift(big_base c, int x){ // 左移x位( * BASE)
		c[0] = c[0] + x;
		for(int i = c[0]; i - x >= 1; --i)
			c[i] = c[i - x];
		for(int i = 1; i <= x; ++i)
			c[i] = 0;
		return c;
	}
	friend big_base rshift(big_base c, int x){
		c[0] = c[0] - x;
		for(int i = 1; i <= c[0]; ++i)
			c[i] = c[i + x];
		return c;
	}
	friend pair<big_base, big_base> divide(big_base a, big_base b){
		if(a[0] < b[0]) return {big_base("0"), a};
		big_base c;
		c[0] = a[0] - b[0] + 1;
		for(int i = c[0]; i >= 1; --i){
			big_base val = lshift(b, i - 1);
			while(cmp(a, val) >= 0){
				a = a - val;
				++c[i];
			}
		}
		while(c[0] > 1 && c[c[0]] == 0) --c[0];
		if(c[0] == 0) c[0]++;
		return {c, a};
	}
	friend big_base operator % (const big_base& a,const big_base& b){
		return divide(a, b).second;
	}
	friend big_base operator / (const big_base& a, const big_base& b){
		return divide(a, b).first;
	}
	operator string(){
		stringstream ss;
		ss << a[a[0]];
		for(int i = a[0] - 1; i >= 1; --i){
			ss << setw(B) << setfill('0') << a[i];
		}
		string ret;
		ss >> ret;
		return ret;
	}
	bool ckzero() const {
		return a[0] == 1 && a[1] == 0;
	}
};
struct big{
	int sgn;
	big_base val;
	void clear(){
		val.clear();
		sgn = 1;
	}
	big(){
		clear();
	}
	big(int val) : big(to_string(val)) {}
	big(ll val) : big(to_string(val)){}
	big(string str){
		clear();
		if(str[0] == '-') {
			str.erase(str.begin());
			sgn = -1;
		}else{
			sgn = 1;
		}
		val = big_base(str);
	}
	big (int sgn_, big_base val_) : sgn(sgn_), val(val_){
		if(val.ckzero()) sgn = 1;
	}
	friend big operator +(big a, big b){
		if(a.sgn == b.sgn)
			return {a.sgn, a.val + b.val};
		if(a.sgn == -1) swap(a, b);
		if(cmp(a.val, b.val) >= 0){
			return {+1, a.val - b.val};
		}else{
			return {-1, b.val - a.val};
		}
	}
	friend big operator - (const big& a, big b){
		b.sgn *= -1;
		return a + b;
	}
	friend big operator * (const big& a, const big& b){
		if(a.sgn == b.sgn){
			return {+1, a.val * b.val};
		}else{
			return {-1, a.val * b.val};
		}
	}
	friend big operator / ( const big& a, const big& b){
		if(a.sgn == b.sgn){
			return {+1, a.val / b.val};
		}else{
			return {-1, a.val / b.val};
		}
	}
	friend big operator % (const big& a, const big& b){
		return a - (a / b) * b;
	}
	operator string(){
		if(sgn == -1) return '-' + string(val);
		else return string(val);
	}
	friend int cmp(const big& a,const big& b){
		if(a.sgn != b.sgn) return a.sgn < b.sgn ? -1 : 1;
		return cmp(a.val, b.val) * a.sgn;
	}
	friend big lshift(big c, int x){ // 左移x位( * BASE)
		return {c.sgn, lshift(c.val, x)};
	}
};
int main(){
	string sa, sb;
	cin >> sa >> sb;
	big a = sa, b = sb;
	return 0;
}```

标签:return,val,符号,int,big,高精度,base,sgn
From: https://www.cnblogs.com/cdsidi/p/17070815.html

相关文章

  • 算法证明中的巨大符号
     数学家为了偷懒,发明了一些缩写符号,由于算法证明中经常出现这些数学符号,对于小学生学习算法非常难懂,所以有必要先弄懂这些数学符号的含义、用法和写法。求和号是数学中......
  • Oracle根据符号分隔字段内字符串后SQL查询数据方法
    --从WITH函数子查询中获取需要的数据SELECTCOUNT(*)FROMCT_BC_BUSINESSCARDFLOWt1WHEREt1.CFSerialNumberNOTIN(--利用WITH函数实现子查询(当做内联视图或者临......
  • 高精度差分
    四、高精度:1.大整数的存储2.模拟加法的存储123+89=212(Ai+Bi+t)#include<vector>将数组的长度变长例题1.高精度减法#include<iostream>#include<vector>using......
  • OLED显示图片和符号+普中51单片机+1.3寸I2C4针
    1实验现象2实验原理OLED(OrganicLight-EmittingDiode)有机发光二极管又称为有机激光显示,OLED显示技术具有自发光的特性,采用非常薄的有机材料涂层,和玻璃基板,当有......
  • 接收一个整型值(无符号),按照顺序打印它的每一位。例如:1234,输出1 2 3 4
    例如:1234,输出1234 #include<stdio.h>voidprint(intn){if(n>9){print(n/10);}printf("%d",n%10);}intmain(){unsignedintnum=0;printf("请输入一......
  • 高精度
    当计算位数超过最大存储范围时,无法正常存储而使用数组来存储数据读取stringa,b;cin>>a>>b;//用字符串读取vector<int>A,B;//转换为存储在数组中for(inti......
  • Latex符号大全
    Part1、希腊/希伯来字符、数学构造符号、分隔符、公式中可变长度的符号、标准函数;Part2、二元运算符和关系符号;Part3、箭头、微积分集合音乐符等杂项、数学mode声......
  • 高精度四则运算
    算法学习的第三天算法学习之高精度四则运算高精度算法(HighAccuracyAlgorithm)是处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然......
  • [简单DP+高精度]围墙重建
    题目描述为了给同学们营造一个良好的学习环境和方便学校的管理,市政府准备对小W就读的学校进行重新规划,占地面积将再次扩大。学校通过领导会议决定,重建学校的围墙。由......
  • typescript中特殊符号(?/!)用法
    1.属性或参数中使用 ?:表示该属性或参数为可选项2. 属性或参数中使用 !:表示强制解析(告诉typescript编译器,这里一定有值),常用于vue-decorator中的@Prop3.变量后使用 !:表......