计算器V3.0.1
2024-10-20 14:14:01
发布于:广东
V3.0.1 修复了加法长度不同会报错的bug.
本次将减少内存,争取做到在Karatsuba算法下空间复杂度从 下降至 .
加,减,朴素乘,二分除、取模,快速幂已完成.
暂时无法实现负数化.
#define version V3.0.1
#define creator cjdst
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct bigInt{
#define lesslen(b){\
bigInt __tmp(b.len + 1);\
__tmp.f = b.f, __tmp.len = b.len;\
copy(&b.a[1], &b.a[b.len + 1], &__tmp.a[1]);\
b = __tmp;\
}
private:
vector <int> a;
int len = 0, f = 1;
inline bigInt mul(const bigInt &a, const bigInt &b){
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--;
lesslen(ans);
return ans;
}
public:
#define check(a, b){if(a < b) return 1; if(a > b) return 0;}
#define CIO const bigInt operator
#define turn bigInt a = *this
#define CIB const bigInt &b
#define VO void operator
#define BO bool operator
explicit bigInt(int n = 0): a(n){}
inline int toint(){
return (len > 2 ? -1 : f * ((len == 2 ? a[2] * (long long)1e9 : 0ll) + a[1]));
}
VO=(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--;
lesslen(tmp);
*this = tmp;
}
VO=(long long n){
bigInt tmp(3);
while(n) tmp.a[++tmp.len] = n % int(1e9), n /= int(1e9);
lesslen(tmp);
*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;}
CIO<<(const int b)const{
bigInt tmp(len + b + 1);
tmp.f = f, tmp.len = len + b;
for(int i = 1; i <= len; i++){
tmp.a[i + b] = a[i];
}
return tmp;
}
CIO>>(const int b)const{
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;
}
BO<(CIB)const{
check(f, b.f) check(len, b.len)
for(int i = len; i >= 1; i--){check(a[i], b.a[i])}
return 0;
}
BO==(CIB)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;
}
CIO+(CIB)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++;
lesslen(ans);
return ans;
}
VO-=(CIB){
if(*this < b){
*this = -(b - *this);
return;
}
for(int i = 1; i <= b.len; i++){
a[i] -= b.a[i];
if(a[i] < 0) a[i] += 1e9, a[i + 1]--;
}
while(!a[len] && len > 1) len--;
lesslen((*this));
}
CIO*(CIB){
return mul(*this, b);
}
CIO*(const int b) const{
bigInt ans(len + 2);
ans.len = len;
for(int i = 1; i <= len; i++){
long long tmp = a[i] * b + ans.a[i];
ans.a[i + 1] = tmp / int(1e9);
ans.a[i] = tmp % int(1e9);
}
if(ans.a[len + 1]) ans.len++;
return ans;
}
CIO/(CIB)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--;
lesslen(ans);
return ans;
}
VO%=(CIB){
if(*this < b) return;
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--;
lesslen((*this));
}
CIO^(int b)const{
bigInt ans(len * b + 1), a = *this;
ans = 1;
while(b){
if(b & 1) ans = ans * a;
a = a * a, b >>= 1;
}
return ans;
}
CIO-()const{turn; a.f = -a.f; return a;}
VO+=(CIB){*this = (*this + b);}
CIO-(CIB)const{turn; a -= b; return a;}
VO*=(CIB){*this = (*this * b);}
VO/=(CIB){*this = (*this / b);}
CIO%(CIB)const{turn; a %= b; return a;}
VO^=(int b){*this = (*this ^ b);}
BO>(CIB)const{return (!(*this < b) && !(*this == b));}
BO<=(CIB)const{return (*this < b || *this == b);}
BO>=(CIB)const{return !(*this < b);}
#undef BO
#undef VO
#undef CIO
#undef CIB
#undef turn
#undef check
}n, m;
int main(){
cin >> n >> m;
cout << n.toint() << endl;
cout << n + m << endl << n - m << endl << n * m << endl << n / m << endl << n % m;
return 0;
}
全部评论 4
666
2天前 来自 广东
0顶
3天前 来自 广东
0该计算器可通过模板题A+-*/%B Problem.
3天前 来自 广东
0顶
3天前 来自 广东
0
有帮助,赞一个