计算器V2.2.1

userId_undefined

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

倔强青铜

2024-09-17 21:15:24

发布于：广东

334阅读
0回复
0点赞

由于递归层数可能过多，所以请在编译选项加入以下命令：

-std=c++11 -Wl,-stack=134217728

预告：开根（明天大概能完成）
V2.2.1修复了小数对大数取模会返回0的bug
V2.2压位工程完成，除法速度提升 22 倍，加、减法速度提升 88 倍，乘法速度提升 3333 倍！ （没办法，因为Base太大，原来的除法已经不适用）
V2.1.1代码优化（似乎啥也没搞但是还是要说）
V2.1更新Karatsuba分治算法，乘法时间复杂度降为 O(n1.6)O(n^{1.6})！！！
V2.0大翻修，回归函数，不使用重载运算符，长度降至3396

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm> 
#define setf a.f = b.f = 1;
#define del0 while(!a.a[a.len]) a.len--; while(!b.a[b.len]) b.len--;
#define optmp while(!tmp.a[tmp.len] && tmp.len > 1) tmp.len--; if(tmp.len <= 0) tmp.len = 1;
using namespace std;
struct INT{
	int a[50005]; 
	int len = 0, f = 1;
	INT(){memset(a, 0, sizeof(a));}
};
//展 示 军 火 
INT input(char*);
INT input(long long);
void print(INT);
INT left(INT, int);
INT right(INT, int);
INT split(INT, int, int);
bool cmp(INT, INT);
INT add(INT, INT);
INT sub(INT, INT);
INT karatsuba(int, INT, INT);
INT __mul(INT, int);
INT mul(INT, INT);
INT div(INT, INT);
INT mod(INT, INT);
INT pow(INT, INT);

INT input(char *a){
	INT tmp;
	int ct = 0;
	while(a[ct] == '-') tmp.f = -tmp.f, ct++;
	int lena = strlen(a);
	int i;
	for(i = lena - 1; i >= ct; i -= 9){
		long long x = 0;
		for(int j = max(ct, i - 8); j <= i; j++){
			x = (x << 3) + (x << 1) + a[j] - '0';
		}
		tmp.a[++tmp.len] = x, x = 0;
	}
	while(!tmp.a[tmp.len] && tmp.len > 1) tmp.len--;
	return tmp;
}
INT input(long long n){
	INT tmp;
	while(n) tmp.a[++tmp.len] = n % int(1e9), n /= int(1e9);
	return tmp;
}
void print(INT tmp){
	if(tmp.f == -1) putchar('-');
	printf("%d", tmp.a[tmp.len]);
	for(int i = tmp.len - 1; i >= 1; i--) printf("%09d", tmp.a[i]);
	putchar('\n');
}

INT left(INT tmp, int b){//左移x位（1000000000进制） 
	INT c;
	c.f = tmp.f, c.len = tmp.len + b;
	for(int i = 1; i <= tmp.len; i++) c.a[i + b] = tmp.a[i];
	return c;
}
INT right(INT tmp, int b){
	INT c;
	c.f = tmp.f, c.len = tmp.len - b;
	for(int i = 1; i <= tmp.len; i++) c.a[i] = tmp.a[i + b];
	return c;
}
INT split(INT n, int st, int l){
	INT tmp;
	for(int i = 1; i <= l; i++){
		tmp.a[i] = n.a[i + st];
	}
	tmp.len = l, tmp.f = n.f;
	return tmp;
}
bool cmp(INT a, INT b){//a是否小于b 
	if(a.f == 1 && b.f == -1) return 0;
	if(a.f == -1 && b.f == 1) return 1;
	if(a.f == -1 && b.f == -1){setf return cmp(b, a);}
	if(a.len > b.len) return 0;
	if(a.len < b.len) return 1;
	for(int i = a.len; i >= 1; i--){
		if(a.a[i] > b.a[i]) return 0;
		if(a.a[i] < b.a[i]) return 1;
	}return 0;
}

INT add(INT a, INT b){//加法 
	INT tmp; del0
	if(a.f == 1 && b.f == -1){setf return sub(a, b);}
	if(a.f == -1 && b.f == 1){setf return sub(b, a);}
	if(a.f == -1 && b.f == -1){setf tmp.f = -1;}
	tmp.len = max(a.len, b.len);
	for(int i = 1; i <= tmp.len; i++){
		tmp.a[i] += a.a[i] + b.a[i];
		if(tmp.a[i] >= 1e9) tmp.a[i + 1]++, tmp.a[i] -= 1e9;
	}
	if(tmp.a[tmp.len + 1]) tmp.len++;
	optmp return tmp;
}

INT sub(INT a, INT b){//减法 
	INT tmp; del0
	if(a.f == 1 && b.f == -1){setf return add(a, b);}
	if(a.f == -1 && b.f == 1){setf tmp = add(a, b), tmp.f = -1; return tmp;}
	if(a.f == -1 && b.f == -1){setf tmp.f = -1;}
	if(cmp(a, b)) swap(a, b), tmp.f = -tmp.f;
	tmp.len = a.len;
	for(int i = 1; i <= tmp.len; i++){
		tmp.a[i] += a.a[i] - b.a[i];
		if(tmp.a[i] < 0) tmp.a[i] += 1e9, tmp.a[i + 1]--;
	}
	optmp return tmp;
}

INT karatsuba(int n, INT a, INT b){//Karatsuba算法 
	INT tmp;
	int f = 1;
	if(a.f == 1 && b.f == -1){setf f = -1;}
	if(a.f == -1 && b.f == 1){setf f = -1;}
	if(a.f == -1 && b.f == -1){setf}
	if(a.len <= 500){
		del0 tmp.len = a.len + b.len;
		for(int i = 1; i <= a.len; i++){
			for(int j = 1; j <= b.len; j++){
				long long ans = 1ll * a.a[i] * b.a[j] + tmp.a[i + j - 1];
				tmp.a[i + j] += ans / int(1e9);
				tmp.a[i + j - 1] = ans % int(1e9);
			}
		}
		optmp
		tmp = left(tmp, n);
		tmp.f = f;
		return tmp;
	}
	int m = a.len >> 1;
	INT ah, al, bh, bl, ac, bd, a_b__d_c;
	ah = split(a, m, a.len - m), al = split(a, 0, m);
	bh = split(b, m, b.len - m), bl = split(b, 0, m);
	ac = karatsuba(n + m * 2, ah, bh), bd = karatsuba(n, al, bl), a_b__d_c = karatsuba(n + m, sub(ah, al), sub(bl, bh));
	tmp = add(add(ac, bd), add(add(right(ac, m), left(bd, m)), a_b__d_c));
	tmp.f = (tmp.f + f == 0 ? -1 : 1);
	return tmp;
}

INT mul(INT a, INT b){
	if(a.len * 50 <= b.len || b.len * 50 <= a.len){
		INT tmp; 
		if(a.f == 1 && b.f == -1){setf tmp.f = -1;}
		if(a.f == -1 && b.f == 1){setf tmp.f = -1;}
		if(a.f == -1 && b.f == -1){setf}
		tmp.len = a.len + b.len;
		for(int i = 1; i <= a.len; i++){
			for(int j = 1; j <= b.len; j++){
				long long ans = 1ll * a.a[i] * b.a[j] + tmp.a[i + j - 1];
				tmp.a[i + j] += ans / int(1e9);
				tmp.a[i + j - 1] = ans % int(1e9);
			}
		}
		optmp
		return tmp;
	}
	a.len = b.len = max(a.len, b.len);
	INT ans = karatsuba(0, a, b);
	if(ans.len <= 0) ans.len = 1;
	return ans;
}
INT __mul(INT a, int b){
	INT tmp;
	tmp.len = a.len + 1;
	for(int i = 1; i <= a.len; i++){
		long long ans = 1ll * a.a[i] * b + tmp.a[i];
		tmp.a[i + 1] = ans / int(1e9);
		tmp.a[i] = ans % int(1e9);
	}
	optmp return tmp;
}

//除法与取余共用一个模板
#define divmod if(a.f == 1 && b.f == -1){setf tmp.f = -1;}\
if(a.f == -1 && b.f == 1){setf tmp.f = -1;}\
if(a.f == -1 && b.f == -1){setf}\
if(cmp(a, b)) return tmp;\
tmp.len = a.len - b.len + 1;\
for(int i = tmp.len; i >= 1; i--){\
	int l = 0, r = 1e9 - 1;\
	while(l <= r){\
		int mid = l + r >> 1;\
		if(!cmp(a, left(__mul(b, mid), i - 1))) l = mid + 1;\
		else r = mid - 1;\
	}\
	a = sub(a, left(__mul(b, r), i - 1));\
	tmp.a[i] = r;\
}optmp
INT div(INT a, INT b){INT tmp; divmod return tmp;}
INT mod(INT a, INT b){INT tmp = a; divmod return a;}

INT pow(INT n, int t){
	INT null;
	null.f = -1, null.len = 0;
	if(t < 0) return null;
	INT tmp = input(1);
	while(t){if(t & 1) tmp = mul(tmp, n); n = mul(n, n), t >>= 1;}
	return tmp;
}

char a[100005], b[100005];
int main(){
	cin >> a >> b;
	INT n = input(a), m = input(b);
	print(div(n, m));
	print(mod(n, m));
	
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 39

热门讨论