本文为各种到处搞来的 C++ 模板
template <class T>
void read(T &n)
{
n = 0;
bool f(false);
char ch;
do
if ((ch = getchar()) == '-')
f = true;
while (ch < '0' || ch > '9');
while ('0' <= ch && ch <= '9')
{
n = (n << 1) + (n << 3) + ch - '0';
ch = getchar();
}
if (f)
n = ~(n - 1);
}
template <class T>
void write(T n)
{
if (n < 0)
{
n = ~(n - 1);
putchar('-');
}
if (n > 9)
write(n / 10);
putchar(n % 10 + '0');
}
template <class T>
inline T gcd(T a, T b)
{
if (a % b == 0)
return a;
return gcd(b, a % b)
}
template <class T>
inline T gcd(T a, T b)
{
while (a ^= b ^= a ^= b %= a)
;
return b;
}
template <class T>
inline T lcm(T a, T b)
{
return T(a * b / gcd(a, b));
}
template <class T>
T pow(T a, T b, T p)
{
T ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
struct Big : vector<int>
{
Big(int n = 0)
{
push_back(n);
check();
}
Big &check()
{
while (!empty() && !back())
pop_back();
if (empty())
return *this;
for (int i = 1; i < size(); ++i)
{
(*this)[i] += (*this)[i - 1] / 10;
(*this)[i - 1] %= 10;
}
while (back() >= 10)
{
push_back(back() / 10);
(*this)[size() - 2] %= 10;
}
return *this;
}
};
istream &operator>>(istream &is, Big &n)
{
string s;
is >> s;
n.clear();
for (int i = s.size() - 1; i >= 0; --i)
n.push_back(s[i] - '0');
return is;
}
ostream &operator<<(ostream &os, const Big &n)
{
if (n.empty())
os << 0;
for (int i = n.size() - 1; i >= 0; --i)
os << n[i];
return os;
}
bool operator!=(const Big &a, const Big &b)
{
if (a.size() != b.size())
return 1;
for (int i = a.size() - 1; i >= 0; --i)
if (a[i] != b[i])
return 1;
return 0;
}
bool operator==(const Big &a, const Big &b)
{
return !(a != b);
}
bool operator<(const Big &a, const Big &b)
{
if (a.size() != b.size())
return a.size() < b.size();
for (int i = a.size() - 1; i >= 0; --i)
if (a[i] != b[i])
return a[i] < b[i];
return 0;
}
bool operator>(const Big &a, const Big &b)
{
return b < a;
}
bool operator<=(const Big &a, const Big &b)
{
return !(a > b);
}
bool operator>=(const Big &a, const Big &b)
{
return !(a < b);
}
Big &operator+=(Big &a, const Big &b)
{
if (a.size() < b.size())
a.resize(b.size());
for (int i = 0; i != b.size(); ++i)
a[i] += b[i];
return a.check();
}
Big operator+(Big a, const Big &b)
{
return a += b;
}
Big &operator-=(Big &a, Big b)
{
if (a < b)
swap(a, b);
for (int i = 0; i != b.size(); a[i] -= b[i], ++i)
if (a[i] < b[i])
{
int j = i + 1;
while (!a[j])
++j;
while (j > i)
{
--a[j];
a[--j] += 10;
}
}
return a.check();
}
Big operator-(Big a, const Big &b)
{
return a -= b;
}
Big operator*(const Big &a, const Big &b)
{
Big n;
n.assign(a.size() + b.size() - 1, 0);
for (int i = 0; i != a.size(); ++i)
for (int j = 0; j != b.size(); ++j)
n[i + j] += a[i] * b[j];
return n.check();
}
Big &operator*=(Big &a, const Big &b)
{
return a = a * b;
}
Big divmod(Big &a, const Big &b)
{
Big ans;
for (int t = a.size() - b.size(); a >= b; --t)
{
Big d;
d.assign(t + 1, 0);
d.back() = 1;
Big c = b * d;
while (a >= c)
{
a -= c;
ans += d;
}
}
return ans;
}
Big operator/(Big a, const Big &b)
{
return divmod(a, b);
}
Big &operator/=(Big &a, const Big &b)
{
return a = a / b;
}
Big &operator%=(Big &a, const Big &b)
{
divmod(a, b);
return a;
}
Big operator%(Big a, const Big &b)
{
return a %= b;
}
Big pow(Big a, int b)
{
Big ans = 1;
while (b)
{
if (b & 1)
ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}