Karatsuba 求卡常

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char IN[10000009]; int PR[19];
const int Mod = 1e8, LEN = 8;
class bigInt {
public:
    vector<int> num; bool neg;
    void shrink() {
        int len = num.size() - 1;
        while (len >= 0 && !num[len]) {num.pop_back(), len--;}
        if (len < 0) num.push_back(0), neg = 0;
    }
    bigInt() {num.clear(); neg = 0;}
    bigInt(vector<int> a, int b) {num = a, neg = b;}
    void clear() {vector<int>().swap(num); neg = 0;}
};
bigInt operator - (const bigInt &x) {return bigInt(x.num, x.neg ^ 1);}
bool operator < (const bigInt &x, const bigInt &y) {
	if (x.neg ^ y.neg) return x.neg;
	if (x.neg) return -y < -x;
	if (x.num.size() ^ y.num.size()) return x.num.size() < y.num.size();
	for (int i = x.num.size() - 1; i >= 0; i--)
		if (x.num[i] ^ y.num[i]) return x.num[i] < y.num[i];
	return 0;
}
bigInt operator - (const bigInt &x, const bigInt &y);
bigInt operator + (const bigInt &x, const bigInt &y) {
	if (x.neg ^ y.neg) {
		if (x.neg) return y - (-x);
		else return x - (-y);
	}
	int lx = x.num.size(), ly = y.num.size(), nl = min(lx, ly), xl = max(lx, ly);
	bigInt res; res.neg = x.neg;
	for (int i = 0; i < nl; ++i) res.num.push_back(x.num[i] + y.num[i]);
	if (lx > ly) for (int i = nl; i < xl; ++i) res.num.push_back(x.num[i]);
	else for (int i = nl; i < xl; ++i) res.num.push_back(y.num[i]);
	res.num.push_back(0);
	for (int i = 0; i < xl; ++i) if (res.num[i] >= Mod) res.num[i + 1]++, res.num[i] -= Mod;
	res.shrink(); return res;
}
bigInt operator - (const bigInt &x, const bigInt &y) {
	if (x.neg || y.neg) {
		if (x.neg && y.neg) return (-y) - (-x);
		else if (x.neg) return -((-x) + y);
		else return x + (-y);
	}
	else if (x < y) return -(y - x);
	int lx = x.num.size(), ly = y.num.size(); bigInt res; res.neg = 0;
	for (int i = 0; i < ly; ++i) res.num.push_back(x.num[i] - y.num[i]);
	for (int i = ly; i < lx; ++i) res.num.push_back(x.num[i]);
	for (int i = 0; i < lx; ++i) if (res.num[i] < 0) res.num[i + 1]--, res.num[i] += Mod;
	res.shrink(); return res;
}
bigInt operator * (const bigInt &x, const bigInt &y) {
	// x=a*10^m+b, y=c*10^m+d
	// x*y=ac*10^(2m)+(ad+bc)*10^m+bd
	int lx = x.num.size(), ly = y.num.size(), n = max(lx, ly), m = (n + 1) >> 1;
	if (n <= 78) {
		bigInt res; res.num.resize(lx + ly);
		for (int i = 0; i < lx; ++i) {
			for (int j = 0; j < ly; ++j) {
				LL T = (LL)x.num[i] * y.num[j];
				res.num[i + j + 1] += ((T + res.num[i + j]) / Mod);
				(res.num[i + j] += (T % Mod)) %= Mod;
			}
		}
		res.shrink(); return res;
	}
	bigInt a, b, c, d;
	for (int i = 0; i < m && i < lx; ++i) b.num.push_back(x.num[i]);
	for (int i = 0; i < m && i < ly; ++i) d.num.push_back(y.num[i]);
	for (int i = m; i < lx; ++i) a.num.push_back(x.num[i]);
	for (int i = m; i < ly; ++i) c.num.push_back(y.num[i]);
	bigInt ac = a * c, bd = b * d, ad = (a + b) * (c + d) - ac - bd;
	ac.num.insert(ac.num.begin(), m << 1, 0), ad.num.insert(ad.num.begin(), m, 0);
	return ac + ad + bd;
}
inline void read(bigInt &x) {
    x.clear(); scanf("%s", IN); int now = 0;
    for (int i = strlen(IN) - 1; i >= 0; i -= LEN) {
        for (int j = max(i - LEN + 1, 0); j <= i; ++j)
            if (IN[j] != '-') now = now * 10 + (IN[j] ^ 48);
            else x.neg = 1;
        x.num.push_back(now), now = 0;
    }
}
inline void write(const bigInt &x, char ch) {
    if (x.neg) putchar('-');
    int len = x.num.size() - 1; bool flag = false;
    for (int i = len; i >= 0; i--) {
    	if (x.num[i] || flag) {
    		if (!flag) printf("%d", x.num[i]);
    		else {
    			for (LL j = 0, X = x.num[i]; j < LEN; ++j, X /= 10) PR[j] = X % 10;
    			for (int j = LEN - 1; j >= 0; j--) putchar(PR[j] ^ 48);
    		}
    		flag = true;
    	}
    }
    if (!flag) putchar('0'); putchar(ch);
}
int main() {
	bigInt a, b; read(a), read(b);
	write(a * b, '\n');
    return 0;
}