计算器V3.1.0

‮队团加不）ด้้童帅_者仇复

2024-11-08 13:35:48

发布于：广东

72阅读

0回复

0点赞

点赞过十开肝负数化+K！！！
V3.1.0 完全实现了对低精运算，字符串自动转换高精.
V3.0.1 修复了加法长度不同会报错的bug.

暂未实现负数化.
时间复杂度如下：（ $N,M$ 分别表示参与运算的两个数的位数， $N\lt M$ ， $^*M$ 表示第二个数本身，低精默认 $M=1$ .
$B$ 代表压的位数，绿色代表常数较小，红色代表常数较大）
加法： $\green{O(N+M)/B}$
减法： $\green{O(N+M)/B}$
乘法： $\green{O(N\times M)/B^2}$
除法： $\red{O(N\times M)/B^2}$
取模： $\red{O(N\times M)/B^2}$
乘方： $\green{O(N^{^*M})}$
乘低精： $\green{O(N/B)}$
除低精： $\green{O(N/B)}$
对低精取模： $\green{O(N/B)}$

#define version V3.1.0
#define creator cjdst

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct bigInt{
	private:
	
	vector <int> a;
	int len = 0, f = 1;
	
	inline const bigInt mul(const bigInt &a, const bigInt &b) const{
		bigInt ans(a.len + b.len + 1);
		ans.len = a.len + b.len;
		for(int i = 1; i <= a.len; i++){
			for(int j = 1; j <= b.len; j++){
				long long tmp = 1ll * a.a[i] * b.a[j] + ans.a[i + j - 1];
				ans.a[i + j] += tmp / int(1e9);
				ans.a[i + j - 1] = tmp % int(1e9);
			}
		}
		while(!ans.a[ans.len] && ans.len > 1) ans.len--;
		ans.a.resize(ans.len + 1);
		return ans;
	}
	
	public:
	
	#define check(a, b){if(a < b) return 1; if(a > b) return 0;}
	#define turn bigInt a = *this
	
	explicit bigInt(int n = 0): a(n){}
	bigInt(const char *s): bigInt(string(s)){}
	bigInt(string s){*this = s;}
	inline long long toint() const{
		return (len > 2 ? -1 : f * ((len == 2 ? a[2] * (long long)1e9 : 0ll) + a[1]));
	}
	pair <bigInt, bigInt> split(int l){
		bigInt tmp1(len - l + 1), tmp2(l + 1);
		tmp1.f = tmp2.f = f;
		tmp1.len = len - l, tmp2.len = l;
		for(int i = 1; i <= l; i++){
			tmp2.a[i] = a[i];
		}
		for(int i = l + 1; i <= len; i++){
			tmp1.a[i - l] = a[i];
		}
		return {tmp1, tmp2};
	}
	
	const bigInt operator = (const string &s){
		bigInt tmp(s.length() / 9 + 2);
		int ct = 0;
		while(s[ct] == '-') tmp.f = -tmp.f, ct++;
		for(int i = s.length() - 1; i >= ct; i -= 9){
			long long x = 0;
			for(int j = max(ct, i - 8); j <= i; j++){
				x = (x << 3) + (x << 1) + s[j] - '0';
			}
			tmp.a[++tmp.len] = x, x = 0;
		}
		while(!tmp.a[tmp.len] && tmp.len > 1) tmp.len--;
		tmp.a.resize(tmp.len + 1);
		return *this = tmp;
	}
	const bigInt operator = (long long n){
		bigInt tmp(3);
		while(n) tmp.a[++tmp.len] = n % int(1e9), n /= int(1e9);
		tmp.a.resize(tmp.len + 1);
		return *this = tmp;
	}
	friend ostream &operator << (ostream &out, bigInt n){
		if(n.f == -1) putchar('-');
		printf("%d", n.a[n.len]);
		for(int i = n.len - 1; i >= 1; i--) printf("%09d", n.a[i]);
		return out;
	}
	friend istream &operator >> (istream &in, bigInt &n){string s; in >> s; n = s; return in;}
	
	const bigInt operator << (const int b) const{
		if(len <= 1 && a[1] == 0) return bigInt(); 
		bigInt tmp(len + b + 1);
		if(len == 1 && !a[1]) return tmp;
		tmp.f = f, tmp.len = len + b;
		for(int i = 1; i <= len; i++){
			tmp.a[i + b] = a[i];
		}
		return tmp;
	}
	const bigInt operator >> (const int b) const{
		if(len < b) return bigInt();
		bigInt tmp(len - b + 1);
		tmp.f = f, tmp.len = len - b;
		for(int i = 1; i <= tmp.len; i++) tmp.a[i] = a[i + b];
		return tmp;
	}
	bool operator < (const bigInt &b) const{
		check(f, b.f) check(len, b.len)
		for(int i = len; i >= 1; i--){check(a[i], b.a[i])}
		return 0;
	}
	bool operator == (const bigInt &b) const{
		if(f != b.f || len != b.len) return 0;
		for(int i = 1; i <= len; i++) if(a[i] != b.a[i]) return 0;
		return 1;
	}
	const bigInt operator + (const bigInt &b) const{
		bigInt ans(max(len, b.len) + 2);
		ans.len = max(len, b.len);
		for(int i = 1; i <= ans.len; i++){
			ans.a[i] += (len >= i ? a[i] : 0) + (b.len >= i ? b.a[i] : 0);
			ans.a[i + 1] = ans.a[i] / int(1e9);
			ans.a[i] %= int(1e9);
		}
		if(ans.a[ans.len + 1]) ans.len++;
		ans.a.resize(ans.len + 1);
		return ans;
	}
	const bigInt operator - (const bigInt &b) const{
		if(*this < b) return -(b - *this);
		bigInt ans = *this;
		for(int i = 1; i <= b.len; i++){
			ans.a[i] -= b.a[i];
			if(ans.a[i] < 0) ans.a[i] += 1e9, ans.a[i + 1]--;
		}
		while(!ans.a[ans.len] && ans.len > 1) ans.len--;
		ans.a.resize(ans.len + 1);
		return ans;
	}
	const bigInt operator * (const bigInt &b) const{
		return mul(*this, b);
	}
	const bigInt operator / (const bigInt &b) const{
		bigInt ans(len - b.len + 2), tmp = *this;
		if(*this < b) return ans;
		ans.len = len - b.len + 1;
		for(int i = ans.len; i >= 1; i--){
			int l = 0, r = 1e9 - 1;
			while(l <= r){
				int mid = l + r >> 1;
				if((b * mid << i - 1) <= tmp) l = mid + 1;
				else r = mid - 1;
			}
			ans.a[i] = r;
			tmp -= (b * r << i - 1);
		}
		while(!ans.a[ans.len] && ans.len > 1) ans.len--;
		ans.a.resize(ans.len + 1);
		return ans;
	}
	const bigInt operator %= (const bigInt &b){
		if(*this < b) return *this;
		int _len = len - b.len + 1;
		for(int i = _len; i >= 1; i--){
			int l = 0, r = 1e9 - 1;
			while(l <= r){
				int mid = l + r >> 1;
				if((b * mid << i - 1) <= *this) l = mid + 1;
				else r = mid - 1;
			}
			*this -= (b * r << i - 1);
		}
		while(!a[len] && len > 1) len--;
		a.resize(len + 1);
		return *this;
	}
	
	const bigInt operator + (const int b) const{
		bigInt tmp;
		tmp = b;
		return *this + tmp;
	}
	const bigInt operator - (const int b) const{
		bigInt tmp;
		tmp = b;
		return *this - tmp;
	}
	const bigInt operator * (const int b) const{
		bigInt ans(len + 2);
		ans.len = len;
		long long tmp = 0;
		for(int i = 1; i <= len; i++){
			tmp = tmp + 1ll * b * a[i];
			ans.a[i] = tmp % int(1e9); 
			tmp /= int(1e9);
		}
		if(tmp) ans.a[++ans.len] = tmp;
		return ans;
	}
	const bigInt operator / (const int b) const{
		bigInt ans(len + 1);
		ans.len = len;
		long long tmp = 0;
		for(int i = len; i >= 1; i--){
			tmp = tmp * int(1e9) + a[i];
			ans.a[i] = tmp / b;
			tmp %= b;
		}
		while(!ans.a[ans.len] && ans.len > 1) ans.len--;
		ans.a.resize(ans.len + 1);
		return ans;
	}
	const int operator % (const int b) const{
		long long tmp = 0;
		for(int i = len; i >= 1; i--){
			tmp = (tmp * int(1e9) + a[i]) % b;
		}
		return tmp;
	}
	const bigInt operator ^ (int b)const{
		bigInt ans, a = *this;
		ans = 1;
		while(b){
			if(b & 1) ans = ans * a;
			a = a * a, b >>= 1;
		}
		return ans;
	}
	
	const bigInt operator - ()const{turn; a.f = -a.f; return a;}
	const bigInt operator += (const bigInt &b){return *this = (*this + b);}
	const bigInt operator -= (const bigInt &b){return *this = (*this - b);}
	const bigInt operator *= (const bigInt &b){return *this = (*this * b);}
	const bigInt operator /= (const bigInt &b){return *this = (*this / b);}
	const bigInt operator % (const bigInt &b) const{turn; a %= b; return a;}
	void operator ^= (const int b){*this = (*this ^ b);}
	bool operator > (const bigInt &b)const{return (!(*this < b) && !(*this == b));}
	bool operator <= (const bigInt &b)const{return (*this < b || *this == b);}
	bool operator >= (const bigInt &b)const{return !(*this < b);}
	const bigInt operator += (const int b){*this = (*this + b);}
	const bigInt operator -= (const int b){*this = (*this - b);}
	const bigInt operator *= (const int b){*this = (*this * b);}
	const bigInt operator /= (const int b){*this = (*this / b);}
	const int operator %= (const int b){*this = (*this % b);}
	
	#undef turn
	#undef check
};
int main(){
	cout << "------计算器------\n暂时无法实现带负数的运算\n";
	while(1){
		cout << "请输入你想要计算的内容：A:加法 B:减法 C:乘法 D:除法 E:取模 F:乘方\n";
		char c;
		cin >> c;
		bigInt a, b;
		cout << "请输入第一个数：\n", cin >> a;
		cout << "请输入第二个数：\n", cin >> b;
		cout << "结果为：\n";
		if(c == 'A') cout << a + b;
		if(c == 'B') cout << a - b;
		if(c == 'C') cout << a * b;
		if(c == 'D') cout << a / b;
		if(c == 'E') cout << a % b;
		if(c == 'F') cout << (a ^ b.toint());
		putchar('\n'); 
	}
	
	return 0;
}