高精度一只

#ifndef BIGINT_H
#define BIGINT_H

#include <string>
#include <vector>
#include <stdexcept>
#include <algorithm>
#include <climits>
#include <cctype>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <cctype>
#include <cstdlib>

class bigint
{
public:
  bigint() : isNegative(false), digits({0}) {}

  // Construct from 64-bit integer
  bigint(int64_t num)
  {
    if (num == LLONG_MIN)
    {
      // Special handling for minimal long value
      digits = {223372036, 854775808}; // -2^63 in base 10^9
      isNegative = true;
      return;
    }

    if (num < 0)
    {
      isNegative = true;
      num = -num;
    }
    else
    {
      isNegative = false;
    }

    if (num == 0)
    {
      digits = {0};
      return;
    }

    // Convert to base 10^9 digits
    while (num > 0)
    {
      digits.push_back(num % BASE);
      num /= BASE;
    }
    std::reverse(digits.begin(), digits.end());
    removeLeadingZeros();
  }

  // Construct from string
  bigint(const std::string &str)
  {
    if (str.empty())
    {
      digits = {0};
      isNegative = false;
      return;
    }

    size_t start = 0;
    if (str[0] == '-')
    {
      isNegative = true;
      start = 1;
    }
    else
    {
      isNegative = false;
    }

    // Skip leading zeros
    while (start < str.size() && str[start] == '0')
    {
      start++;
    }

    if (start == str.size())
    {
      digits = {0};
      isNegative = false;
      return;
    }

    // Process digits in chunks of 9
    for (size_t i = str.size(); i > start; i -= DIGITS_PER_ELEMENT)
    {
      size_t chunkStart = (i >= DIGITS_PER_ELEMENT) ? (i - DIGITS_PER_ELEMENT) : start;
      std::string chunk = str.substr(chunkStart, i - chunkStart);
      digits.push_back(std::stoul(chunk));
    }

    std::reverse(digits.begin(), digits.end());
    removeLeadingZeros();
  }

  // Copy and move constructors
  bigint(const bigint &other) = default;
  bigint(bigint &&other) = default;

  // Assignment operators
  bigint &operator=(const bigint &other) = default;
  bigint &operator=(bigint &&other) = default;

  ~bigint() = default;

  // Read from input stream
  static bigint read(std::istream &is)
  {
    std::string s;
    is >> s;
    return bigint(s);
  }

  // Arithmetic operations
  bigint operator-() const;
  bigint operator+(const bigint &other) const;
  bigint operator-(const bigint &other) const;
  bigint operator*(const bigint &other) const;
  bigint operator/(const bigint &other) const;
  bigint operator%(const bigint &other) const;

  // Compound assignment operators
  bigint &operator+=(const bigint &other);
  bigint &operator-=(const bigint &other);
  bigint &operator*=(const bigint &other);
  bigint &operator/=(const bigint &other);
  bigint &operator%=(const bigint &other);

  // Comparison operators
  bool operator==(const bigint &other) const;
  bool operator!=(const bigint &other) const;
  bool operator<(const bigint &other) const;
  bool operator<=(const bigint &other) const;
  bool operator>(const bigint &other) const;
  bool operator>=(const bigint &other) const;

  // Conversion operators
  explicit operator std::string() const;
  explicit operator int64_t() const;
  explicit operator bool() const;

  // Utility functions
  void print() const;
  bigint abs() const;
  bool isZero() const;

  // Data members
  bool isNegative;
  std::vector<uint32_t> digits;

  // Constants for base 10^9 representation
  static const uint64_t BASE = 1000000000; // 10^9 base
  static const size_t DIGITS_PER_ELEMENT = 9;

private:
  // Internal helpers
  void removeLeadingZeros();
  int compare(const bigint &other) const;

  // Arithmetic implementations
  bigint add(const bigint &other) const;
  bigint subtract(const bigint &other) const;
  bigint multiply(const bigint &other) const;

  // Division helpers
  bigint divide(const bigint &other) const;
  bigint mod(const bigint &other) const;

  // Karatsuba multiplication components
  bigint karatsuba(const bigint &x, const bigint &y) const;
  bigint shiftLeft(size_t n) const;
};

// Remove leading zero digits
void bigint::removeLeadingZeros()
{
  auto it = digits.begin();
  while (it != digits.end() - 1 && *it == 0)
  {
    ++it;
  }
  digits.erase(digits.begin(), it);
  if (digits.empty())
  {
    digits.push_back(0);
  }
}

// Compare two bigints (-1: this < other, 0: equal, 1: this > other)
int bigint::compare(const bigint &other) const
{
  if (isNegative != other.isNegative)
  {
    return isNegative ? -1 : 1;
  }

  if (digits.size() != other.digits.size())
  {
    bool comp = digits.size() < other.digits.size();
    return isNegative ? (comp ? 1 : -1) : (comp ? -1 : 1);
  }

  for (size_t i = 0; i < digits.size(); i++)
  {
    if (digits[i] != other.digits[i])
    {
      bool comp = digits[i] < other.digits[i];
      return isNegative ? (comp ? 1 : -1) : (comp ? -1 : 1);
    }
  }

  return 0;
}

// Unary minus operator
bigint bigint::operator-() const
{
  bigint result = *this;
  if (!isZero())
  {
    result.isNegative = !isNegative;
  }
  return result;
}

// Addition operator
bigint bigint::operator+(const bigint &other) const
{
  if (isNegative == other.isNegative)
  {
    bigint result = add(other);
    result.isNegative = isNegative;
    return result;
  }

  if (abs() < other.abs())
  {
    bigint result = other.subtract(*this);
    result.isNegative = other.isNegative;
    return result;
  }

  bigint result = subtract(other);
  result.isNegative = isNegative;
  return result;
}

// Subtraction operator
bigint bigint::operator-(const bigint &other) const
{
  return *this + (-other);
}

// Multiplication operator using optimal algorithm selection
bigint bigint::operator*(const bigint &other) const
{
  bigint result = multiply(other);
  result.isNegative = isNegative != other.isNegative;
  result.removeLeadingZeros();
  return result;
}

// Division operator
bigint bigint::operator/(const bigint &other) const
{
  if (other.isZero())
  {
    throw std::invalid_argument("Division by zero");
  }

  bigint result = divide(other);
  result.isNegative = isNegative != other.isNegative;
  result.removeLeadingZeros();
  return result;
}

// Modulo operator
bigint bigint::operator%(const bigint &other) const
{
  if (other.isZero())
  {
    throw std::invalid_argument("Division by zero");
  }

  bigint result = mod(other);
  result.isNegative = isNegative;
  result.removeLeadingZeros();
  return result;
}

// Compound addition assignment
bigint &bigint::operator+=(const bigint &other)
{
  *this = *this + other;
  return *this;
}

// Compound subtraction assignment
bigint &bigint::operator-=(const bigint &other)
{
  *this = *this - other;
  return *this;
}

// Compound multiplication assignment
bigint &bigint::operator*=(const bigint &other)
{
  *this = *this * other;
  return *this;
}

// Compound division assignment
bigint &bigint::operator/=(const bigint &other)
{
  *this = *this / other;
  return *this;
}

// Compound modulo assignment
bigint &bigint::operator%=(const bigint &other)
{
  *this = *this % other;
  return *this;
}

// Equality comparison
bool bigint::operator==(const bigint &other) const
{
  return compare(other) == 0;
}

// Inequality comparison
bool bigint::operator!=(const bigint &other) const
{
  return compare(other) != 0;
}

// Less than comparison
bool bigint::operator<(const bigint &other) const
{
  return compare(other) < 0;
}

// Less than or equal comparison
bool bigint::operator<=(const bigint &other) const
{
  return compare(other) <= 0;
}

// Greater than comparison
bool bigint::operator>(const bigint &other) const
{
  return compare(other) > 0;
}

// Greater than or equal comparison
bool bigint::operator>=(const bigint &other) const
{
  return compare(other) >= 0;
}

// Convert to string representation
bigint::operator std::string() const
{
  if (isZero())
  {
    return "0";
  }

  std::string str;
  if (isNegative)
  {
    str += '-';
  }

  // First digit without leading zeros
  str += std::to_string(digits[0]);

  // Remaining digits with leading zeros
  for (size_t i = 1; i < digits.size(); i++)
  {
    std::string digit = std::to_string(digits[i]);
    str += std::string(DIGITS_PER_ELEMENT - digit.size(), '0') + digit;
  }

  return str;
}

// Convert to int64_t
bigint::operator int64_t() const
{
  int64_t num = 0;
  for (uint32_t digit : digits)
  {
    if (num > (LLONG_MAX / static_cast<int64_t>(BASE)) ||
        (num *= BASE) > LLONG_MAX - digit)
    {
      throw std::overflow_error("bigint too large for int64_t");
    }
    num = num * BASE + digit;
  }
  return isNegative ? -num : num;
}

// Convert to boolean
bigint::operator bool() const
{
  return !isZero();
}

// Absolute value
bigint bigint::abs() const
{
  bigint result = *this;
  result.isNegative = false;
  return result;
}

// Check if zero
bool bigint::isZero() const
{
  return digits.size() == 1 && digits[0] == 0;
}

// Print bigint to stdout
void bigint::print() const
{
  if (isNegative)
  {
    printf("-");
  }
  printf("%u", digits[0]);
  for (size_t i = 1; i < digits.size(); i++)
  {
    printf("%09u", digits[i]);
  }
}

// Add two bigints (same sign)
bigint bigint::add(const bigint &other) const
{
  bigint result;
  result.digits.clear();

  size_t i = digits.size();
  size_t j = other.digits.size();
  uint64_t carry = 0;

  while (i > 0 || j > 0 || carry > 0)
  {
    uint64_t sum = carry;
    if (i > 0)
      sum += digits[--i];
    if (j > 0)
      sum += other.digits[--j];

    carry = sum / BASE;
    result.digits.push_back(sum % BASE);
  }

  std::reverse(result.digits.begin(), result.digits.end());
  result.removeLeadingZeros();
  return result;
}

// Subtract two bigints (this > other, same sign)
bigint bigint::subtract(const bigint &other) const
{
  bigint result;
  result.digits.clear();

  size_t i = digits.size();
  size_t j = other.digits.size();
  int64_t borrow = 0;

  while (i > 0)
  {
    int64_t diff = digits[--i] - borrow;
    if (j > 0)
      diff -= other.digits[--j];

    if (diff < 0)
    {
      borrow = 1;
      diff += BASE;
    }
    else
    {
      borrow = 0;
    }

    result.digits.push_back(diff);
  }

  std::reverse(result.digits.begin(), result.digits.end());
  result.removeLeadingZeros();
  return result;
}

// Multiplication dispatcher
bigint bigint::multiply(const bigint &other) const
{
  // Handle simple cases
  if (isZero() || other.isZero())
    return bigint(0);
  if (*this == 1)
    return other;
  if (other == 1)
    return *this;

  // Use Karatsuba for numbers larger than 10 digits
  if (digits.size() > 10 || other.digits.size() > 10)
  {
    return karatsuba(*this, other);
  }

  // Naive multiplication for small numbers
  bigint result;
  result.digits.resize(digits.size() + other.digits.size(), 0);

  for (size_t i = 0; i < digits.size(); i++)
  {
    uint64_t carry = 0;
    for (size_t j = 0; j < other.digits.size(); j++)
    {
      uint64_t product = static_cast<uint64_t>(digits[i]) * other.digits[j] +
                         result.digits[i + j] + carry;
      carry = product / BASE;
      result.digits[i + j] = product % BASE;
    }

    if (carry > 0)
    {
      result.digits[i + other.digits.size()] = carry;
    }
  }

  result.removeLeadingZeros();
  return result;
}

// Karatsuba multiplication (O(n^log3))
bigint bigint::karatsuba(const bigint &x, const bigint &y) const
{
  // Base case for small numbers
  if (x.digits.size() < 10 || y.digits.size() < 10)
  {
    return x.multiply(y);
  }

  // Split at half the max length
  size_t m = std::max(x.digits.size(), y.digits.size()) / 2;

  // Split x and y into high and low parts
  bigint xHigh = x;
  bigint xLow;
  if (m < x.digits.size())
  {
    xHigh.digits.erase(xHigh.digits.begin(), xHigh.digits.begin() + (x.digits.size() - m));
    xLow.digits = std::vector<uint32_t>(x.digits.end() - m, x.digits.end());
  }
  else
  {
    xLow = x;
  }

  bigint yHigh = y;
  bigint yLow;
  if (m < y.digits.size())
  {
    yHigh.digits.erase(yHigh.digits.begin(), yHigh.digits.begin() + (y.digits.size() - m));
    yLow.digits = std::vector<uint32_t>(y.digits.end() - m, y.digits.end());
  }
  else
  {
    yLow = y;
  }

  // Recursive steps
  bigint z0 = karatsuba(xLow, yLow);
  bigint z1 = karatsuba((xLow + xHigh), (yLow + yHigh));
  bigint z2 = karatsuba(xHigh, yHigh);

  // Combine results
  bigint temp = z1 - z2 - z0;
  bigint result = z2.shiftLeft(2 * m) + temp.shiftLeft(m) + z0;

  result.removeLeadingZeros();
  return result;
}

// Shift left by n digits (base 10^9)
bigint bigint::shiftLeft(size_t n) const
{
  if (isZero())
  {
    return *this;
  }

  bigint result = *this;
  result.digits.insert(result.digits.begin(), n, 0);
  return result;
}

// Division implementation
bigint bigint::divide(const bigint &divisor) const
{
  // Handle division by zero
  if (divisor.isZero())
  {
    throw std::invalid_argument("Division by zero");
  }

  bigint dividend = abs();
  bigint div = divisor.abs();

  // Special case: dividend < divisor
  if (dividend < div)
  {
    return bigint(0);
  }

  // Special case: divisor is single digit
  if (div.digits.size() == 1)
  {
    bigint quotient;
    quotient.digits.clear();
    uint64_t carry = 0;

    for (size_t i = 0; i < dividend.digits.size(); i++)
    {
      uint64_t current = carry * BASE + dividend.digits[i];
      quotient.digits.push_back(current / div.digits[0]);
      carry = current % div.digits[0];
    }

    quotient.removeLeadingZeros();
    return quotient;
  }

  // Long division for multi-digit divisor
  bigint quotient;
  bigint remainder;

  for (size_t i = 0; i < dividend.digits.size(); i++)
  {
    remainder = remainder.shiftLeft(1) + bigint(static_cast<int64_t>(dividend.digits[i]));
    if (remainder < div)
    {
      quotient.digits.push_back(0);
    }
    else
    {
      // Estimate quotient digit
      uint64_t q = (remainder.digits.size() > div.digits.size()) ? (static_cast<uint64_t>(remainder.digits[0]) * BASE + remainder.digits[1]) / div.digits[0] : remainder.digits[0] / div.digits[0];

      q = std::min(q, BASE - 1);

      // Adjust quotient digit
      while (bigint(static_cast<int64_t>(q)) * div > remainder)
      {
        q--;
      }

      quotient.digits.push_back(q);
      remainder = remainder - bigint(static_cast<int64_t>(q)) * div;
    }
  }

  quotient.removeLeadingZeros();
  return quotient;
}

// Modulo implementation
bigint bigint::mod(const bigint &divisor) const
{
  bigint quotient = *this / divisor;
  return *this - quotient * divisor;
}

#endif