---
# System prepended metadata

title: infinite_int
tags: [codebook]

---

---
tags: codebook
---

# infinite_int

{%hackmd theme-dark %}
```cpp=
//#pragma once
#include<iostream>
#include<iomanip>
#include<vector>
#include<cmath>
#include<cassert>
#include<algorithm>
using namespace std;
//#define NDEBUG
static constexpr unsigned limit = 1000000000;
class infinite_int {
private:
	int m_sgn;
	vector<unsigned> m_data;

//輔助函數
	friend bool uless   (const infinite_int& a, const infinite_int& b);//
	friend bool ugreater(const infinite_int& a, const infinite_int& b);//
	friend const infinite_int& umax(const infinite_int& a, const infinite_int& b);//
	friend const infinite_int& umin(const infinite_int& a, const infinite_int& b);//
	infinite_int& shrink();//
	infinite_int& lshift(unsigned x);
	infinite_int& rshift(unsigned x);
	friend infinite_int karatsuba(infinite_int a, infinite_int b);

public:
//建構元
	infinite_int(const long long& x);//
	infinite_int(string str);//
	infinite_int(const infinite_int& x);//

//解構元
	~infinite_int();//

//串流運算子
	friend ostream& operator<<(ostream& os, const infinite_int& x);//
	friend istream& operator>>(istream& is, infinite_int& x);//

//算數運算子
	friend infinite_int operator-(infinite_int a);//
	friend const infinite_int& operator+(const infinite_int& a);//

	friend infinite_int operator+(const infinite_int& a, const infinite_int& b);//
	friend infinite_int operator-(const infinite_int& a, const infinite_int& b);//
	friend infinite_int operator*(const infinite_int& a, const infinite_int& b);
	friend infinite_int operator/(const infinite_int& a, const infinite_int& b);

	friend infinite_int& operator+=(infinite_int& a, const infinite_int& b);//
	friend infinite_int& operator-=(infinite_int& a, const infinite_int& b);//
	friend infinite_int& operator*=(infinite_int& a, const infinite_int& b);
	friend infinite_int& operator/=(infinite_int& a, const infinite_int& b);

//位元運算子
	friend infinite_int operator&(const infinite_int& a, const infinite_int& b);
	friend infinite_int operator|(const infinite_int& a, const infinite_int& b);
	friend infinite_int operator^(const infinite_int& a, const infinite_int& b);
	friend infinite_int operator<<(const infinite_int& a, const unsigned& b);
	friend infinite_int operator>>(const infinite_int& a, const unsigned& b);

	friend infinite_int& operator&=(infinite_int& a, const infinite_int& b);
	friend infinite_int& operator|=(infinite_int& a, const infinite_int& b);
	friend infinite_int& operator^=(infinite_int& a, const infinite_int& b);
	friend infinite_int& operator<<=(infinite_int& a, const unsigned& b);
	friend infinite_int& operator>>=(infinite_int& a, const unsigned& b);

//比較運算子
	friend bool operator==(const infinite_int& a, const infinite_int& b);//
	friend bool operator!=(const infinite_int& a, const infinite_int& b);//
	friend bool operator< (const infinite_int& a, const infinite_int& b);//
	friend bool operator<=(const infinite_int& a, const infinite_int& b);//
	friend bool operator> (const infinite_int& a, const infinite_int& b);//
	friend bool operator>=(const infinite_int& a, const infinite_int& b);//

};
bool uless(const infinite_int& a, const infinite_int& b) {
	if (a.m_data.size() != b.m_data.size())
		return a.m_data.size() < b.m_data.size();
	for (size_t i = a.m_data.size(); i; i--)
		if (a.m_data.at(i - 1) != b.m_data.at(i - 1))
			return a.m_data.at(i - 1) < b.m_data.at(i - 1);
	return false;
}
bool ugreater(const infinite_int& a, const infinite_int& b) {
	if (a.m_data.size() != b.m_data.size())
		return a.m_data.size() > b.m_data.size();
	for (size_t i = a.m_data.size(); i; i--)
		if (a.m_data.at(i - 1) != b.m_data.at(i - 1))
			return a.m_data.at(i - 1) > b.m_data.at(i - 1);
	return false;
}
const infinite_int& umax(const infinite_int& a, const infinite_int& b) {
	return uless(a, b) ? b : a;
}
const infinite_int& umin(const infinite_int& a, const infinite_int& b) {
	return uless(a, b) ? a : b;
}
infinite_int& infinite_int::shrink() {
	while (m_data.size() > 1 && !m_data.back())
		m_data.pop_back();
	if (m_data.size() && !m_data.back())
		m_sgn = 0;
	return *this;
}
infinite_int& infinite_int::lshift(unsigned x) {
	size_t size = m_data.size();
	m_data.resize(size + x, 0);
	for (size_t i = size; i; i--)
		m_data.at(x + i - 1) = m_data.at(i - 1);
	return shrink();
}
infinite_int& infinite_int::rshift(unsigned x) {
	if (x >= m_data.size())
		return *this = 0;
	for (size_t i = 0; i != m_data.size() - x; i++)
		m_data.at(i) = m_data.at(i + x);
	m_data.resize(m_data.size() - x);
	return shrink();
}
infinite_int karatsuba(infinite_int a, infinite_int b) {
	a.shrink(), b.shrink();
//	cout << "original a: " << a << endl;
//	cout << "original b: " << b << endl;
	if (min(a.m_data.size(), b.m_data.size()) <= 32) {
		infinite_int ret = 0;
		long long tmp = 0;
		ret.m_data.resize(a.m_data.size() + b.m_data.size() + 1, 0);
		for (size_t i = 0; i != a.m_data.size(); i++) {
			for (size_t j = 0; j != b.m_data.size(); j++)
				tmp += static_cast<long long>(a.m_data.at(i)) * b.m_data.at(j) + ret.m_data.at(i + j),
				       ret.m_data.at(i + j) = tmp % limit, tmp /= limit;
			ret.m_data.at(i + b.m_data.size()) += tmp, tmp = 0;
		}
		ret.m_sgn = a.m_sgn * b.m_sgn;
//		cout << "O(n^2): " << ret.shrink() << endl;
		return ret.shrink();
	}
	size_t m = min(a.m_data.size(), b.m_data.size()) / 2;
	infinite_int ap = a, bp = b;
	a.rshift(m), b.rshift(m);
	ap.m_data.resize(m), bp.m_data.resize(m);
	ap.shrink(), bp.shrink();
//	cout << "a: " << a << endl << "b: " << b << endl;
//	cout << "ap: " << ap << endl << "bp: " << bp << endl;
	infinite_int z0 = karatsuba(ap, bp);
	infinite_int z1 = karatsuba(a + ap, b + bp);
	infinite_int z2 = karatsuba(a, b);
//	cout << "z0: " << z0 << endl << "z1: " << z1 << endl << "z2: " << z2 << endl;
	z0 += (z2.lshift(m) + z1 - z2 - z0).lshift(m);
	return z0.shrink();
}
unsigned _abs(long long x) {
	return x >= 0 ? x : -x;
}
infinite_int::infinite_int(const long long& x = 0):
	m_sgn(x ? (x > 0 ? 1 : -1) : 0), m_data{_abs(x % limit), _abs(x / limit)}
{shrink();}
infinite_int::infinite_int(string str) {
	m_sgn = 1;
	if (str.front() == '-')
		m_sgn = -1, str = str.substr(1);
	while (str.size() >= 9)
		m_data.push_back(atoi(str.substr(str.size() - 9).data())), str.resize(str.size() - 9);
	if (str.size())
		m_data.push_back(atoi(str.data()));
	shrink();
}
infinite_int::infinite_int(const infinite_int& x):
	m_sgn(x.m_sgn), m_data(x.m_data)
{shrink();}
infinite_int::~infinite_int() {}
ostream& operator<<(ostream& os, const infinite_int& x) {
	os << (x.m_sgn == -1 ? "-" : "") << x.m_data.back();
	for (auto i = next(x.m_data.crbegin()); i != x.m_data.crend(); i++)
		os << setfill('0') << setw(9) << *i;
	return os;
}
istream& operator>>(istream& is, infinite_int& x) {
	string str;
	is >> str;
	x = infinite_int(str);
	return is;
}
infinite_int operator-(infinite_int a) {
	a.m_sgn *= -1; return a;
}
const infinite_int& operator+(const infinite_int& a) {
	return a;
}
infinite_int operator+(const infinite_int& a, const infinite_int& b) {
	if (!a.m_sgn || !b.m_sgn)
		return a.m_sgn ? a : b;
	const infinite_int& refa = umin(a, b);
	const infinite_int& refb = umax(a, b);
	assert(refa.m_data.size() <= refb.m_data.size());
	infinite_int c;
	c.m_data.resize(refb.m_data.size() + 1, 0);
	long long tmp = 0;
	if (a.m_sgn * b.m_sgn == 1) {
		for (size_t i = 0; i < refa.m_data.size(); i++)
			assert(i < refa.m_data.size()), assert(i < refb.m_data.size()),
			       tmp += refa.m_data.at(i) + refb.m_data.at(i), c.m_data.at(i) = tmp % limit, tmp /= limit;
		for (size_t i = refa.m_data.size(); i < refb.m_data.size(); i++)
			assert(i < refb.m_data.size()),
			       tmp += refb.m_data.at(i), c.m_data.at(i) = tmp % limit, tmp /= limit;
	} else {
		for (size_t i = 0; i < refa.m_data.size(); i++)
			assert(i < refa.m_data.size()), assert(i < refb.m_data.size()),
			       tmp += static_cast<long long>(limit) + refb.m_data.at(i), tmp -= refa.m_data.at(i),
			               c.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
		for (size_t i = refa.m_data.size(); i < refb.m_data.size(); i++)
			assert(i < refb.m_data.size()),
			       tmp += limit + refb.m_data.at(i), c.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
	}
	c.m_data.back() = tmp, c.m_sgn = refb.m_sgn;
	return c.shrink();
}
infinite_int& operator+=(infinite_int& a, const infinite_int& b) {
	if (!a.m_sgn) {a = b; return a.shrink();}
	if (!b.m_sgn) {return a.shrink();}
	a.m_data.resize(max(a.m_data.size(), b.m_data.size()) + 1, 0);
	long long tmp = 0;
	if (a.m_sgn * b.m_sgn == 1) {
		for (size_t i = 0; i < b.m_data.size(); i++)
			assert(i < a.m_data.size()), assert(i < b.m_data.size()),
			       tmp += a.m_data.at(i) + b.m_data.at(i), a.m_data.at(i) = tmp % limit, tmp /= limit;
	} else {
		if (uless(a, b)) {
			for (size_t i = 0; i < b.m_data.size(); i++)
				assert(i < a.m_data.size()), assert(i < b.m_data.size()),
				       tmp += static_cast<long long>(limit) + b.m_data.at(i) - a.m_data.at(i), a.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
			a.m_sgn = b.m_sgn;
		} else {
			for (size_t i = 0; i < b.m_data.size(); i++)
				assert(i < a.m_data.size()), assert(i < b.m_data.size()),
				       tmp += static_cast<long long>(limit) + a.m_data.at(i) - b.m_data.at(i), a.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
		}
	}
	a.m_data.at(b.m_data.size()) = tmp;
	return a.shrink();
}
infinite_int operator-(const infinite_int& a, const infinite_int& b) {
	if (!a.m_sgn || !b.m_sgn)
		return a.m_sgn ? a : b;
	const infinite_int& refa = umin(a, b);
	const infinite_int& refb = umax(a, b);
	assert(refa.m_data.size() <= refb.m_data.size());
	infinite_int c;
	c.m_data.resize(refb.m_data.size() + 1, 0);
	long long tmp = 0;
	if (a.m_sgn * -b.m_sgn == 1) {
		for (size_t i = 0; i < refa.m_data.size(); i++)
			assert(i < refa.m_data.size()), assert(i < refb.m_data.size()),
			       tmp += refa.m_data.at(i) + refb.m_data.at(i), c.m_data.at(i) = tmp % limit, tmp /= limit;
		for (size_t i = refa.m_data.size(); i < refb.m_data.size(); i++)
			assert(i < refb.m_data.size()),
			       tmp += refb.m_data.at(i), c.m_data.at(i) = tmp % limit, tmp /= limit;
	} else {
		for (size_t i = 0; i < refa.m_data.size(); i++)
			assert(i < refa.m_data.size()), assert(i < refb.m_data.size()),
			       tmp += static_cast<long long>(limit) + refb.m_data.at(i) - refa.m_data.at(i), c.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
		for (size_t i = refa.m_data.size(); i < refb.m_data.size(); i++)
			assert(i < refb.m_data.size()),
			       tmp += static_cast<long long>(limit) + refb.m_data.at(i), c.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
	}
	c.m_data.back() = tmp, c.m_sgn = &a == &refb ? refb.m_sgn : refb.m_sgn * -1;
	return c.shrink();
}
infinite_int& operator-=(infinite_int& a, const infinite_int& b) {
	if (!a.m_sgn) {a = b, a.m_sgn = -1; return a.shrink();}
	if (!b.m_sgn) {return a.shrink();}
	a.m_data.resize(max(a.m_data.size(), b.m_data.size()) + 1, 0);
	long long tmp = 0;
	if (a.m_sgn * -b.m_sgn == 1) {
		for (size_t i = 0; i < b.m_data.size(); i++)
			assert(i < a.m_data.size()), assert(i < b.m_data.size()),
			       tmp += a.m_data.at(i) + b.m_data.at(i), a.m_data.at(i) = tmp % limit, tmp /= limit;
	} else {
		if (uless(a, b)) {
			for (size_t i = 0; i < b.m_data.size(); i++)
				assert(i < a.m_data.size()), assert(i < b.m_data.size()),
				       tmp += limit + b.m_data.at(i) - a.m_data.at(i), a.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
			a.m_sgn = -b.m_sgn;
		} else {
			for (size_t i = 0; i < b.m_data.size(); i++)
				assert(i < a.m_data.size()), assert(i < b.m_data.size()),
				       tmp += limit + a.m_data.at(i) - b.m_data.at(i), a.m_data.at(i) = tmp % limit, tmp /= limit, tmp--;
		}
	}
	a.m_data.at(b.m_data.size()) = tmp;
	return a.shrink();
}
infinite_int operator*(const infinite_int& a, const infinite_int& b) {return karatsuba(a, b);}
infinite_int& operator*=(infinite_int& a, const infinite_int& b) {return a = a * b;}
bool operator< (const infinite_int& a, const infinite_int& b) {
	return a.m_sgn != b.m_sgn ? a.m_sgn <  b.m_sgn : uless(a, b) ^ (a.m_sgn == -1);
}
bool operator<=(const infinite_int& a, const infinite_int& b) {
	return a.m_sgn != b.m_sgn ? a.m_sgn <= b.m_sgn : !ugreater(a, b) ^ (a.m_sgn == -1);
}
bool operator> (const infinite_int& a, const infinite_int&b) {
	return a.m_sgn != b.m_sgn ? a.m_sgn >  b.m_sgn : ugreater(a, b) ^ (a.m_sgn == -1);
}
bool operator>=(const infinite_int& a, const infinite_int&b) {
	return a.m_sgn != b.m_sgn ? a.m_sgn >= b.m_sgn : !uless(a, b) ^ (a.m_sgn == -1);
}
bool operator==(const infinite_int& a, const infinite_int& b) {
	if (a.m_sgn != b.m_sgn || a.m_data.size() != b.m_data.size())
		return false;
	for (size_t i = 0; i != a.m_data.size(); i++)
		if (a.m_data[i] != b.m_data[i])
			return false;
	return true;
}
bool operator!=(const infinite_int& a, const infinite_int& b) {
	if (a.m_sgn != b.m_sgn || a.m_data.size() != b.m_data.size())
		return true;
	for (size_t i = 0; i != a.m_data.size(); i++)
		if (a.m_data[i] != b.m_data[i])
			return true;
	return false;
}
infinite_int pow(infinite_int a, unsigned long long b) {
	infinite_int ret = 1;
	for (; b; b >>= 1, a *= a)
		if (b & 1) ret *= a;
	return ret;
}
int main() {
	infinite_int a;
	unsigned long long b;
	while (cin >> a >> b)
		cout << pow(a, b) << endl;
	return 0;
}
```