#include <cmath>
#include <stack>
#include "maths.h"
/*
说明：本源码遵循BSD开源协议：使用、修改时，请不要修改命名空间
*/
namespace ljs
{
char Integer::dec2hex(Integer c) const
{
if (c == 0 || c._data.size() == 0)
{
return '0';
}
else if (c == 1)
{
return '1';
}
else if (c == 2)
{
return '2';
}
else if (c == 3)
{
return '3';
}
else if (c == 4)
{
return '4';
}
else if (c == 5)
{
return '5';
}
else if (c == 6)
{
return '6';
}
else if (c == 7)
{
return '7';
}
else if (c == 8)
{
return '8';
}
else if (c == 9)
{
return '9';
}
else if (c == 10)
{
return 'a';
}
else if (c == 11)
{
return 'b';
}
else if (c == 12)
{
return 'c';
}
else if (c == 13)
{
return 'd';
}
else if (c == 14)
{
return 'e';
}
else if (c == 15)
{
return 'f';
}
return '0';
}
Integer::Integer()
{
clear();
}
Integer::Integer(long long num)
{
clear();
do {
_data.push_back(num % _base);
num = num / _base;
} while (num > 0);
}
Integer::Integer(const std::string str)
{
clear();
if (str.length() == 0)
{
return;
}
if (str.at(0) == '-')
{
_sign = false;
}
int x;
long long len = (str.length() - 1) / 8 + 1;
for (int i = 0; i < len; i++)
{
long long end = str.length() - i * 8;
long long start = max(0, end - 8);
sscanf_s(str.substr(start, end - start).c_str(), "%d", &x);
_data.push_back(x);
}
}
Integer::~Integer()
{
clear();
}
void Integer::clear()
{
_data.clear();
_sign = true;
}
size_t Integer::length() const
{
size_t x = 0;
if (_data.size() > 0)
{
x += 8 * (_data.size() - 1);
int y = _data.at(_data.size() - 1);
for (; y > 0; ++x) y /= 10;
}
return x;
}
short Integer::bit(size_t i) const
{
return (int(_data.at(i / 8))) / (int(std::pow(10, i % 8))) % 10;
}
bool Integer::is_odd() const
{
return !is_even();
}
bool Integer::is_even() const
{
return bit(0) % 2 == 0;
}
Integer Integer::hex_str(const std::string str)
{
clear();
std::string hexs = "";
long long n = str.length();
int s = 0;
int d;
Integer tp;
while (--n > -1)
{
tp = "16";
tp = tp.power(n);
if (str.at(s) <= '9' && str.at(s) >= '0')
{
d = str.at(s) - '0';
}
else if (str.at(s) <= 'f' && str.at(s) >= 'a')
{
d = str.at(s) - 'a';
d += 10;
}
else if (str.at(s) <= 'F' && str.at(s) >= 'A')
{
d = str.at(s) - 'A';
d += 10;
}
s++;
tp = tp * d;
*this += tp;
}
return *this;
}
std::string Integer::hex_str() const
{
std::string hexs;
hexs = "";
Integer tp = *this;
while (tp > 0)
{
hexs = dec2hex(tp % 16) + hexs;
tp = tp / 16;
}
return hexs;
}
Integer Integer::dec_str(const std::string str)
{
*this = str;
return *this;
}
std::string Integer::dec_str() const
{
std::string res;
res = "";
for (int i = 0; i < _data.size(); i++)
{
if (i == _data.size() - 1)
{
std::string sstemp = std::to_string(_data.at(i));
res = sstemp + res;
}
else
{
int n = _data.at(i);
char temp[10];
memset(temp, 0, 10);
sprintf_s(temp, 10, "%08d", n);
res = temp + res;
}
}
if (res == "")
res = "0";
if (!_sign && res != "0")
res = "-" + res;
return res;
}
Integer Integer::operator=(long long num)
{
clear();
do {
_data.push_back(num % _base);
num = num / _base;
} while (num > 0);
return *this;
}
Integer Integer::operator=(const std::string str)
{
clear();
if (str.length() == 0)
{
return *this;
}
if (str.at(0) == '-')
{
_sign = false;
}
int x;
long long len = (str.length() - 1) / 8 + 1;
for (int i = 0; i < len; i++)
{
long long end = str.length() - i * 8;
long long start = max(0, end - 8);
sscanf_s(str.substr(start, end - start).c_str(), "%d", &x);
_data.push_back(x);
}
return *this;
}
bool Integer::operator<(const Integer& num) const
{
if (!_sign && num._sign)
{
return true;
}
if (_sign && !num._sign)
{
return false;
}
if (!_sign && !num._sign)
{
Integer a = *this;
a._sign = true;
Integer b = num;
b._sign = true;
return b < a;
}
if (_data.size() != num._data.size())
return _data.size() < num._data.size();
for (long long i = _data.size() - 1; i >= 0; i--)
if (_data.at(i) != num._data.at(i))
return _data.at(i) < num._data.at(i);
return false;
}
bool Integer::operator>(const Integer& num)const
{
return num < *this;
}
bool Integer::operator<=(const Integer& num)const
{
return !(*this > num);
}
bool Integer::operator>=(const Integer& num)const
{
return !(*this < num);
}
bool Integer::operator!=(const Integer& num)const
{
return *this > num || *this < num;
}
bool Integer::operator==(const Integer& num)const
{
return !(num != *this);
}
Integer Integer::operator+(const Integer& num) const
{
if (_sign ^ num._sign)
{
Integer tmp = _sign ? num : *this;
tmp._sign = true;
return _sign ? *this - tmp : num - tmp;
}
Integer c;
int g = 0;
for (int i = 0;; i++)
{
if (g == 0 && i >= _data.size() && i >= num._data.size()) break;
int x = g;
if (i < _data.size())
{
x += _data.at(i);
}
if (i < num._data.size())
{
x += num._data.at(i);
}
c._data.push_back(x % _base);
g = x / _base;
}
while (g > 0)
{
c._data.push_back(g % _base);
g = g / _base;
}
c._sign = _sign;
return c;
}
Integer Integer::operator++()
{
*this = *this + 1;
return *this;
}
Integer Integer::operator+=(const Integer& num)
{
*this = *this + num;
return *this;
}
Integer Integer::operator-(const Integer& num) const
{
Integer a = *this, b = num;
if (!num._sign && !_sign)
{
b._sign = true;
a._sign = true;
return b - a;
}
if (!b._sign)
{
b._sign = true;
return a + b;
}
if (!a._sign)
{
a._sign = true;
b = a + b;
b._sign = false;
return b;
}
Integer c;
if (a == b)
{
return c;
}
if (a < b)
{
c = (b - a);
c._sign = false;
return c;
}
int i;
int h = 0;
int x = 0;
for (i = 0; i < b._data.size(); i++)
{
int m = a._data.at(i) - h;
int n = b._data.at(i);
if (m < n)
{
h = 1;
m += _base;
x += (m - n);
}
else
{
h = 0;
x += (m - n);
}
c._data.push_back(x % _base);
x = x / _base;
}
x -= h;
for (; i < a._data.size(); i++) {
x += a._data[i];
c._data.push_back(x % _base);
x = x / _base;
}
while (x > 0)
{
c._data.push_back(x % _base);
x = x / _base;
}
while (c._data.at(c._data.size() - 1) == 0)
{
c._data.pop_back();
}
return c;
}
Integer Integer::operator--()
{
*this = *this - 1;
return *this;
}
Integer Integer::operator-=(const Integer& num)
{
*this = *this - num;
return *this;
}
Integer Integer::operator*(const Integer& num)const
{
Integer b;
for (int i = 0; i < _data.size(); i++)
{
Integer c;
long long g = 0;
long long x = 0;
for (int k = 0; k < i; k++)
{
c._data.push_back(0);
}
long long m = _data.at(i);
for (int j = 0; j < num._data.size(); j++)
{
long long n = num._data.at(j);
x = g + m * n;
c._data.push_back(x % _base);
g = x / _base;
}
while (g > 0)
{
c._data.push_back(g % _base);
g = g / _base;
}
b += c;
}
b._sign = !(_sign ^ num._sign);
return b;
}
Integer Integer::operator*=(const
