分治高精乘 成功！

Karatsuba算法，时间复杂度 $O(n^{1.6})$（约等于 $O(n\sqrt{n})$），但常数有亿点大

#include <iostream>
#include <cstdio>
#include <cstring>
#include <memory.h>
#define setf a.f = b.f = 1;
#define del0 while(a.a[a.len] == 0 && a.len > 1) a.len--; while(b.a[b.len] == 0 && b.len > 1) b.len--;
using namespace std;
struct INT{
	char a[20005];
	INT(){
		memset(a, 0, sizeof(a));
	}
	int len = 1, f = 1;
}n, m;
INT add(INT, INT);
INT sub(INT, INT);
char a[20005];
bool cmp(INT a, INT b){
	if(a.len < b.len) return 1;
	if(a.len > b.len) return 0;
	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;
}
void input(char *a, INT &n){
	n.len = strlen(a);
	for(int i = 1; i <= n.len; i++){
		n.a[i] = a[n.len - i] - '0';
	}
	while(n.a[n.len] == -3) n.a[n.len--] = 0, n.f = -n.f;
	while(!n.a[n.len] && n.len > 1) n.len--;
}
void print(INT n){
	if(n.f == -1) putchar('-');
	for(int i = n.len; i >= 1; i--){
		putchar(n.a[i] + '0');
	}
	putchar('\n');
}
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;
}
INT left(INT tmp, int b){//左移x位（10进制） 
	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 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] >= 10) tmp.a[i + 1]++, tmp.a[i] -= 10;
	}
	if(tmp.a[tmp.len + 1]) tmp.len++;
	while(tmp.a[tmp.len] == 0 && tmp.len > 1) tmp.len--;
	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] += 10, tmp.a[i + 1]--;
	}
	while(tmp.a[tmp.len] == 0 && tmp.len > 1) tmp.len--;
	return tmp;
}
INT karatsuba(int n, INT a, INT b){//n表示10的几次方 
	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 <= 2000){
		del0 tmp.len = a.len + b.len;
		for(int i = 1; i <= a.len; i++){
			for(int j = 1; j <= b.len; j++){
				tmp.a[i + j - 1] += a.a[i] * b.a[j];
				tmp.a[i + j] += tmp.a[i + j - 1] / 10;
				tmp.a[i + j - 1] %= 10;
			}
		}
		while(!tmp.a[tmp.len] && tmp.len > 1) tmp.len--;
		tmp = left(tmp, n);
		tmp.f = f;
		return tmp;
	}
	int m = a.len >> 1;
	INT ah = split(a, m, a.len - m), al = split(a, 0, m);
	INT bh = split(b, m, b.len - m), bl = split(b, 0, m);
	INT 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){
	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 main(){
	cin >> a;
	input(a, n);
	cin >> a;
	input(a, m);
	int midlen = n.len >> 1;
	print(mul(n, m));

	return 0;
}