高精度
__H_J_M__
·
·
算法·理论
class INT {
private:
static const int BASE = 10000; // 万进制
static const int BASE_DIGITS = 4; // 每4位一组
std::vector<int> digits; // 小端序存储（低位在前）
bool sign; // true为非负，false为负
// 移除前导零并处理0的符号
void trim() {
while (digits.size() > 1 && digits.back() == 0)
digits.pop_back();
if (digits.size() == 1 && digits[0] == 0)
sign = true; // 确保0的符号为正
}
// 比较绝对值大小（忽略符号）
int compareAbs(const INT& other) const {
if (digits.size() != other.digits.size())
return digits.size() < other.digits.size() ? -1 : 1;
for (int i = digits.size() - 1; i >= 0; --i) {
if (digits[i] != other.digits[i])
return digits[i] < other.digits[i] ? -1 : 1;
}
return 0;
}
public:
// 构造函数
INT() : digits(1, 0), sign(true) {}
INT(long long num) {
*this = INT(std::to_string(num));
}
INT(const std::string& s) {
sign = true;
int len = s.size();
int start = 0;
// 处理符号
if (s[0] == '-') {
sign = false;
start = 1;
} else if (s[0] == '+') {
start = 1;
}
// 跳过前导零
while (start < len - 1 && s[start] == '0')
start++;
// 按4位分组
digits.clear();
for (int i = len - 1; i >= start; i -= BASE_DIGITS) {
int num = 0;
for (int j = std::max(start, i - BASE_DIGITS + 1); j <= i; ++j) {
num = num * 10 + (s[j] - '0');
}
digits.push_back(num);
}
if (digits.empty()) digits.push_back(0);
trim();
}
// 拷贝构造函数
INT(const INT& other) = default;
// 赋值运算符
INT& operator=(const INT& other) = default;
// 转换为字符串
std::string toString() const {
if (digits.empty()) return "0";
std::string res;
if (!sign) res += '-';
res += std::to_string(digits.back());
for (int i = digits.size() - 2; i >= 0; --i) {
std::string s = std::to_string(digits[i]);
res += std::string(BASE_DIGITS - s.size(), '0') + s;
}
return res;
}
// 友元输入输出
friend std::ostream& operator<<(std::ostream& out, const INT& num) {
out << num.toString();
return out;
}
friend std::istream& operator>>(std::istream& in, INT& num) {
std::string s;
in >> s;
num = INT(s);
return in;
}
// 比较运算符
bool operator<(const INT& other) const {
if (sign != other.sign)
return !sign;
return sign ? compareAbs(other) < 0 : compareAbs(other) > 0;
}
bool operator>(const INT& other) const { return other < *this; }
bool operator<=(const INT& other) const { return !(other < *this); }
bool operator>=(const INT& other) const { return !(*this < other); }
bool operator==(const INT& other) const {
return sign == other.sign && digits == other.digits;
}
bool operator!=(const INT& other) const { return !(*this == other); }
// 算术运算符
INT operator-() const {
INT res = *this;
if (res != INT(0)) res.sign = !res.sign;
return res;
}
INT operator+(const INT& other) const {
if (sign == other.sign) {
INT res;
res.sign = sign;
res.digits.assign(std::max(digits.size(), other.digits.size()) + 1, 0);
for (int i = 0; i < res.digits.size() - 1; ++i) {
int a = i < digits.size() ? digits[i] : 0;
int b = i < other.digits.size() ? other.digits[i] : 0;
res.digits[i] += a + b;
if (res.digits[i] >= BASE) {
res.digits[i] -= BASE;
res.digits[i + 1]++;
}
}
res.trim();
return res;
}
return *this - (-other);
}
INT operator-(const INT& other) const {
if (sign == other.sign) {
if (compareAbs(other) >= 0) {
INT res;
res.sign = sign;
res.digits.resize(digits.size());
int borrow = 0;
for (int i = 0; i < digits.size(); ++i) {
int a = digits[i];
int b = i < other.digits.size() ? other.digits[i] : 0;
int temp = a - b - borrow;
if (temp < 0) {
temp += BASE;
borrow = 1;
} else {
borrow = 0;
}
res.digits[i] = temp;
}
res.trim();
return res;
}
return -(other - *this);
}
return *this + (-other);
}
INT operator*(const INT& other) const {
INT res;
res.digits.assign(digits.size() + other.digits.size(), 0);
res.sign = (sign == other.sign);
for (int i = 0; i < digits.size(); ++i) {
int carry = 0;
for (int j = 0; j < other.digits.size() || carry; ++j) {
long long cur = res.digits[i + j] +
(long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) +
carry;
res.digits[i + j] = cur % BASE;
carry = cur / BASE;
}
}
res.trim();
return res;
}
INT operator/(const INT& other) const {
if (other == INT(0)) throw std::runtime_error("Division by zero");
INT res, cur;
res.sign = (sign == other.sign);
res.digits.assign(digits.size(), 0);
for (int i = digits.size() - 1; i >= 0; --i) {
cur = cur * BASE + digits[i];
int l = 0, r = BASE;
while (l < r) {
int mid = (l + r) / 2;
if (other.abs() * mid <= cur) {
l = mid + 1;
} else {
r = mid;
}
}
res.digits[i] = r - 1;
cur -= other.abs() * (r - 1);
}
res.trim();
return res;
}
INT operator%(const INT& other) const {
return *this - (*this / other) * other;
}
// 赋值运算符
INT& operator+=(const INT& other) { *this = *this + other; return *this; }
INT& operator-=(const INT& other) { *this = *this - other; return *this; }
INT& operator*=(const INT& other) { *this = *this * other; return *this; }
INT& operator/=(const INT& other) { *this = *this / other; return *this; }
INT& operator%=(const INT& other) { *this = *this % other; return *this; }
// 幂运算（快速幂）
INT pow(long long exponent) const {
if (exponent < 0) return pow(-exponent).inverse();
INT res(1), base = *this;
while (exponent) {
if (exponent & 1) res = res * base;
base = base * base;
exponent >>= 1;
}
return res;
}
// 绝对值
INT abs() const {
INT res = *this;
res.sign = true;
return res;
}
// 倒数（用于负指数幂）
INT inverse() const {
if (*this == INT(0))
throw std::runtime_error("Division by zero");
return INT(1) / *this;
}
// 常用常量
static INT zero() { return INT(0); }
static INT one() { return INT(1); }
static INT ten() { return INT(10); }
};