---
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;
}
```
Sign in with Wallet
Connect another wallet