---
tags: codebook
---

{%hackmd theme-dark %}

# unlimited_int

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<sstream>
using namespace std;

constexpr int limit = 1e9;
constexpr int limit_digit = log10(limit);

struct unlimited_int {
	vector<int> data; bool negative;
	operator bool() {
		return data.size() > 1 && !data.back();
	}
	void swap(unlimited_int& x) {
		auto datat = move(x.data);
		auto negativet = move(x.negative);
		x.data = data, x.negative = negative;
		data = datat, negative = negativet;
	}
	unlimited_int& shrink() {
		while (data.size() > 1 && !data.back())
			data.pop_back();
		long long n = 0;
		for (size_t i = 0; i != data.size(); i++) {
			data[i] = (n += data[i] + limit) % limit, n /= limit, n--;
		}
		return *this;
	}
	unlimited_int(const int& x): data(1, abs(x)), negative(x > 0) {}
	unlimited_int(const string& s = ""): negative(!s.empty() && s.front() == '-') {
		for (int i = s.size(); i >= limit_digit + negative; i -= limit_digit)
			data.push_back(atoi(string(s.begin() + i - limit_digit, s.begin() + i).data()));
		data.push_back(
		    atoi((string(s.begin() + negative, s.begin() + negative + (s.size() - negative) % limit_digit)).data()));
		shrink();
	}
};
istream& operator>>(istream& is, unlimited_int& x) {
	string s; is >> s; size_t n = 0;
	while (n < s.size() && !(s[n] == '-' || isdigit(s[n]))) n++;
	unlimited_int(s.substr(n)).swap(x); return is;
}
string utos(const unlimited_int& x) {
	string str, tmp; char c[limit_digit + 1]; size_t n;
	for (auto i = x.data.crbegin() + 1; i < x.data.crend(); i++)
		n = sprintf(c, "%d", *i), str += string(limit_digit - n, '0') + string(c, n);
	n = sprintf(c, "%d", x.data.back());
	return string(x.negative, '-') + string(c, n) + str;
}
unlimited_int operator<<(const unlimited_int& a, size_t b) {
	unlimited_int c; c.data.assign(b, 0);
	c.data.insert(c.data.end(), a.data.cbegin(), a.data.cend());
	return c.shrink();
}
ostream& operator<<(ostream& os, const unlimited_int& x) {
	string str, tmp; char c[limit_digit + 1];
	size_t n = sprintf(c, "%d", x.data.back());
	os << string(x.negative, '-') << string(c, n);
	for (auto i = x.data.crbegin() + 1; i < x.data.crend(); i++)
		n = sprintf(c, "%d", *i), os << string(limit_digit - n, '0') + string(c, n);
	return os;
}
unlimited_int operator-(unlimited_int a) {
	a.negative = !a.negative; return a;
}
unlimited_int uabs(unlimited_int x) {
	x.negative = false; return x;
}
bool operator==(const unlimited_int& a, const unlimited_int& b) {
	if ((a.negative ^ b.negative) | (a.data.size() ^ b.data.size()))
		return false;
	for (size_t i = 0; i != a.data.size(); i++)
		if (a.data[i] ^ b.data[i])
			return false;
	return true;
}
bool operator<(const unlimited_int& a, const unlimited_int& b) {
	if (a.negative != b.negative)
		return a.negative > b.negative;
	if (a.data.size() != b.data.size())
		return a.negative ^ (a.data.size() < b.data.size());
	for (size_t i = a.data.size() - 1; i >= 0; i--)
		if (a.data[i] != b.data[i])
			return a.negative ^ (a.data[i] < b.data[i]);
	return false;
}
bool operator!=(const unlimited_int& a, const unlimited_int& b) {
	return !(a == b);
}
bool operator<=(const unlimited_int& a, const unlimited_int& b) {
	return (a == b) | (a < b);
}
bool operator>(const unlimited_int& a, const unlimited_int& b) {
	return !(a <= b);
}
bool operator>=(const unlimited_int& a, const unlimited_int& b) {
	return !(a < b);
}
unlimited_int operator+(const unlimited_int& a, const unlimited_int& b) {
	bool cmp = uabs(a) > uabs(b);
	const auto& ra(cmp ? a : b);
	const auto& rb(cmp ? b : a);
	long long n = 0; unlimited_int c;
	c.data.assign(max(ra.data.size(), rb.data.size()) + 1, 0);
	for (size_t i = 0; i != rb.data.size(); i++) {
		if (a.negative ^ b.negative)
			c.data[i] = (n += ra.data[i] - rb.data[i]) % limit, n /= limit;
		else
			c.data[i] = (n += ra.data[i] + rb.data[i]) % limit, n /= limit;
	}
	for (size_t i = rb.data.size(); i < ra.data.size(); i++)
		c.data[i] = (n += ra.data.at(i)) % limit, n /= limit;
	c.data.back() = n;
	c.negative = ra.negative;
	return c.shrink();
}
unlimited_int operator-(const unlimited_int& a, const unlimited_int& b) {
	return a + (-b);
}
size_t hibit(size_t n) {
	n |= (n >>  1);
	n |= (n >>  2);
	n |= (n >>  4);
	n |= (n >>  8);
	n |= (n >> 16);
	return n - (n >> 1);
}
unlimited_int karatsuba(const unlimited_int& a, const unlimited_int& b) {
	if (a.data.size() <= 3 || b.data.size() <= 3) {
		unlimited_int c; long long n = 0;
		c.data.resize(a.data.size() + b.data.size(), 0);
		for (size_t i = 0, j; i != a.data.size(); i++) {
			for (j = 0; j != b.data.size(); j++)
				c.data[i + j] = (n += c.data[i + j] + static_cast<long long>(a.data[i]) * b.data[j]) % limit, n /= limit;
			while (n) c.data[i + j] = (n += c.data[i + j]) % limit, n /= limit;
		}
		return c.shrink();
	}
	unlimited_int ca(a), cb(b);
	size_t m = max(a.data.size(), b.data.size());
	m = hibit(m) << bool(m ^ hibit(m));
	ca.data.resize(m), cb.data.resize(m), m >>= 1;
	unlimited_int a1, a2, b1, b2, c;
	a1.data.assign(ca.data.begin(), ca.data.begin() + m);
	a2.data.assign(ca.data.begin() + m, ca.data.end());
	b1.data.assign(cb.data.begin(), cb.data.begin() + m);
	b2.data.assign(cb.data.begin() + m, cb.data.end());
	unlimited_int z1 = karatsuba(a1, b1);
	unlimited_int z2 = karatsuba(a1 + a2, b2 + b1);
	unlimited_int z3 = karatsuba(a2, b2);
	return ((z3 << 2 * m) + ((z2 - z3 - z1) << m) + z1).shrink();
}
unlimited_int operator*(const unlimited_int& a, const unlimited_int& b) {
	return karatsuba(a, b).shrink();
}
unlimited_int& operator*=(unlimited_int& a, const unlimited_int& b) {
	return a = a * b;
}
unlimited_int pow(unlimited_int a, unsigned long long b) {
	unlimited_int ans(1);
	for (; b; a *= a, b >>= 1)
		if (b & 1) ans *= a;
	return ans;
}
int main() {
	unlimited_int a, b;
//	unsigned long long b;
	while (cin >> a >> b)
		cout << a * b << endl;
	return 0;
}