A1.A+B problem题解

我们都知道，这道题非常深奥，我们可能需要使用高精度。
献上我的617行代码：

#include<bits/stdc++.h>
using namespace std;
template<typename T>
T my_max(T a, T b) {
    if (a > b) return a;
    return b;
}//赠送求最大和最小模板
template<typename T>
T my_min(T a, T b) {
    if (a < b) return a;
    return b;
}
class bignum{
private:
    static const int MAX_DIGITS;
    static const int BASE;
    static const int BASE_DIGITS;
    int digits[1005];
    int length;
    bool isnegative;
    void normalize() {
        while (length > 1 && digits[length - 1] == 0) {
            length--;
        }
        if (length == 1 && digits[0] == 0) {
            isnegative = false;
        }
    }
    int compareabs(const bignum& other) const {
        if (length != other.length) {
            if (length > other.length) return 1;
            return -1;
        }
        for (int i = length - 1; i >= 0; i--) {
            if (digits[i] != other.digits[i]) {
                if (digits[i] > other.digits[i]) return 1;
                return -1;
            }
        }
        return 0;
    }
    void setZero() {
        memset(digits, 0, sizeof(digits));
        digits[0] = 0;
        length = 1;
        isnegative = false;
    }
    void parseFromString(const string& str) {
        setZero();
        if (str.empty()) return;
        int start = 0;
        if (str[0] == '-') {
            isnegative = true;
            start = 1;
        } else if (str[0] == '+')start = 1;
        while (start < (int)str.length() && str[start] == '0')start++;
        if (start == (int)str.length()) {
            setZero();
            return;
        }
        int totalDigits = str.length() - start;
        int groups = (totalDigits + BASE_DIGITS - 1) / BASE_DIGITS;
        length = 0;
        for (int i = 0; i < groups; i++) {
            int end = str.length() - i * BASE_DIGITS;
            int startPos = (start > end - BASE_DIGITS) ? start : (end - BASE_DIGITS);
            string groupStr = str.substr(startPos, end - startPos);
            digits[length++] = atoi(groupStr.c_str());
        }
        normalize();
    }
public:
    bignum() { setZero(); }
    bignum(long long num) {
        setZero();
        if (num == 0) return;
        if (num < 0) {
            isnegative = true;
            num = -num;
        }
        length = 0;
        while (num > 0) {
            digits[length++] = num % BASE;
            num /= BASE;
        }
    }
    bignum(int num) {
        setZero();
        if (num == 0) return;
        if (num < 0) {
            isnegative = true;
            num = -num;
        }
        length = 0;
        while (num > 0) {
            digits[length++] = num % BASE;
            num /= BASE;
        }
    }
    bignum(unsigned long long num) {
        setZero();
        if (num == 0) return;
        length = 0;
        while (num > 0) {
            digits[length++] = num % BASE;
            num /= BASE;
        }
    }
    bignum(const string& str) { parseFromString(str); }
    bignum(const char* str) { parseFromString(string(str)); }
    bignum(const bignum& other) {
        memcpy(digits, other.digits, sizeof(digits));
        length = other.length;
        isnegative = other.isnegative;
    }
    bignum& operator=(const bignum& other) {
        if (this != &other) {
            memcpy(digits, other.digits, sizeof(digits));
            length = other.length;
            isnegative = other.isnegative;
        }
        return *this;
    }
    bignum& operator=(long long num) { return *this = bignum(num); }
    bignum& operator=(int num) { return *this = bignum(num); }
    bignum& operator=(unsigned long long num) { return *this = bignum(num); }
    bignum& operator=(const string& str) { return *this = bignum(str); }
    bignum& operator=(const char* str) { return *this = bignum(str); }
    bool readnum() {
        setZero();
        int ch = getchar();
        while (ch == ' ' || ch == '\n' || ch == '\t' || ch == '\r')ch = getchar();
        if (ch == EOF) return false;
        if (ch == '-') {
            isnegative = true;
            ch = getchar();
        } else if (ch == '+')ch = getchar();
        if (ch < '0' || ch > '9') {
            if (ch != EOF) ungetc(ch, stdin);
            return true;
        }
        string numStr = "";
        while (ch >= '0' && ch <= '9') {
            numStr += (char)ch;
            ch = getchar();
        }
        if (ch != EOF) ungetc(ch, stdin);
        parseFromString((isnegative ? "-" : "") + numStr);
        return true;
    }
    string toString() const {
        if (length == 1 && digits[0] == 0) return "0";
        string result;
        if (isnegative) result += '-';
        char buffer[20];
        sprintf(buffer, "%d", digits[length - 1]);
        result += buffer;
        for (int i = length - 2; i >= 0; i--) {
            char group[10];
            sprintf(group, "%04d", digits[i]);
            result += group;
        }
        return result;
    }
    char* toCStr() const {
        string str = toString();
        char* result = new char[str.length() + 1];
        strcpy(result, str.c_str());
        return result;
    }
    void print() const {
        if (isnegative) printf("-");
        printf("%d", digits[length - 1]);
        for (int i = length - 2; i >= 0; i--) {
            printf("%04d", digits[i]);
        }
    }
    bool operator<(const bignum& other) const {
        if (isnegative != other.isnegative)return isnegative;
        if (length != other.length) {
            if (isnegative)return length > other.length;
            else return length < other.length;
        }
        for (int i = length - 1; i >= 0; i--) {
            if (digits[i] != other.digits[i]) {
                if (isnegative) {
                    return digits[i] > other.digits[i];
                } else return digits[i] < other.digits[i];
            }
        }
        return false;
    }
    bool operator==(const bignum& other) const {
        if (isnegative != other.isnegative || length != other.length)return false;
        for (int i = 0; i < length; i++) {
            if (digits[i] != other.digits[i])return false;
        }
        return true;
    }
    bool operator!=(const bignum& other) const { return !(*this == other); }
    bool operator<=(const bignum& other) const { return *this < other || *this == other; }
    bool operator>(const bignum& other) const { return !(*this <= other); }
    bool operator>=(const bignum& other) const { return !(*this < other); }
    bignum operator+(const bignum& other) const {
        if (isnegative != other.isnegative) {
            if (isnegative) {
                return other - (-*this);
            } else {
                return *this - (-other);
            }
        }
        bignum result;
        result.isnegative = isnegative;
        result.length = my_max(length, other.length);
        int carry = 0;
        for (int i = 0; i < result.length; i++) {
            int sum = carry;
            if (i < length) sum += digits[i];
            if (i < other.length) sum += other.digits[i];
            result.digits[i] = sum % BASE;
            carry = sum / BASE;
        }
        if (carry > 0 && result.length < MAX_DIGITS) {
            result.digits[result.length++] = carry;
        }
        result.normalize();
        return result;
    }
    bignum operator-(const bignum& other) const {
        if (isnegative != other.isnegative) return *this + (-other);
        int cmp = compareabs(other);
        if (cmp == 0) return bignum(0);
        if (cmp < 0) {
            bignum result = other - *this;
            result.isnegative = !isnegative;
            return result;
        }
        bignum result;
        result.isnegative = isnegative;
        result.length = length;
        int borrow = 0;
        for (int i = 0; i < result.length; i++) {
            int diff = digits[i] - borrow;
            if (i < other.length) {
                diff -= other.digits[i];
            }
            if (diff < 0) {
                diff += BASE;
                borrow = 1;
            } else {
                borrow = 0;
            }
            result.digits[i] = diff;
        }
        result.normalize();
        return result;
    }
    bignum operator*(const bignum& other) const {
        bignum result;
        result.isnegative = isnegative != other.isnegative;
        for (int i = 0; i < length; i++) {
            long long carry = 0;
            for (int j = 0; j < other.length || carry > 0; j++) {
                if (i + j >= MAX_DIGITS) break;
                long long product = result.digits[i + j] + carry;
                if (j < other.length) product += (long long)digits[i] * other.digits[j];
                result.digits[i + j] = product % BASE;
                carry = product / BASE;
            }
        }
        result.length = my_min(MAX_DIGITS, length + other.length);
        result.normalize();
        return result;
    }
    bignum operator/(const bignum& other) const {
        if (other == bignum(0)) throw "Division by zero";
        bignum dividend = abs();
        bignum divisor = other.abs();
        if (dividend < divisor) return bignum(0);
        bignum result;
        result.isnegative = isnegative != other.isnegative;
        result.length = length;
        bignum current;
        for (int i = length - 1; i >= 0; i--) {
            current = current * BASE + digits[i];
            current.normalize();
            int left = 0, right = BASE - 1;
            int quotient = 0;
            while (left <= right) {
                int mid = (left + right) / 2;
                bignum product = divisor * mid;
                if (product <= current) {
                    quotient = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            result.digits[i] = quotient;
            current = current - divisor * quotient;
        }
        result.normalize();
        return result;
    }
    bignum operator%(const bignum& other) const {return *this - (*this / other) * other;}
    template<typename T>
    bignum operator+(T other) const { return *this + bignum(other); }
    template<typename T>
    bignum operator-(T other) const { return *this - bignum(other); }
    template<typename T>
    bignum operator*(T other) const { return *this * bignum(other); }
    template<typename T>
    bignum operator/(T other) const { return *this / bignum(other); }
    template<typename T>
    bignum operator%(T other) const { return *this % bignum(other); }
    template<typename T>
    friend bignum operator+(T lhs, const bignum& rhs) { return bignum(lhs) + rhs; }
    template<typename T>
    friend bignum operator-(T lhs, const bignum& rhs) { return bignum(lhs) - rhs; }
    template<typename T>
    friend bignum operator*(T lhs, const bignum& rhs) { return bignum(lhs) * rhs; }
    template<typename T>
    friend bignum operator/(T lhs, const bignum& rhs) { return bignum(lhs) / rhs; }
    template<typename T>
    friend bignum operator%(T lhs, const bignum& rhs) { return bignum(lhs) % rhs; }
    friend bignum operator+(const char* lhs, const bignum& rhs) { return bignum(lhs) + rhs; }
    friend bignum operator+(const string& lhs, const bignum& rhs) { return bignum(lhs) + rhs; }
    friend bignum operator-(const char* lhs, const bignum& rhs) { return bignum(lhs) - rhs; }
    friend bignum operator-(const string& lhs, const bignum& rhs) { return bignum(lhs) - rhs; }
    friend bignum operator*(const char* lhs, const bignum& rhs) { return bignum(lhs) * rhs; }
    friend bignum operator*(const string& lhs, const bignum& rhs) { return bignum(lhs) * rhs; }
    friend bignum operator/(const char* lhs, const bignum& rhs) { return bignum(lhs) / rhs; }
    friend bignum operator/(const string& lhs, const bignum& rhs) { return bignum(lhs) / rhs; }
    friend bignum operator%(const char* lhs, const bignum& rhs) { return bignum(lhs) % rhs; }
    friend bignum operator%(const string& lhs, const bignum& rhs) { return bignum(lhs) % rhs; }
    bignum operator-() const {
        bignum result = *this;
        if (result != bignum(0)) {
            result.isnegative = !result.isnegative;
        }
        return result;
    }
    bignum& operator++() {
        *this = *this + bignum(1);
        return *this;
    }
    bignum operator++(int) {
        bignum temp = *this;
        ++(*this);
        return temp;
    }
    bignum& operator--() {
        *this = *this - bignum(1);
        return *this;
    }
    bignum operator--(int) {
        bignum temp = *this;
        --(*this);
        return temp;
    }
    bignum& operator+=(const bignum& other) { return *this = *this + other; }
    bignum& operator-=(const bignum& other) { return *this = *this - other; }
    bignum& operator*=(const bignum& other) { return *this = *this * other; }
    bignum& operator/=(const bignum& other) { return *this = *this / other; }
    bignum& operator%=(const bignum& other) { return *this = *this % other; }
    template<typename T>
    bignum& operator+=(T other) { return *this = *this + bignum(other); }
    template<typename T>
    bignum& operator-=(T other) { return *this = *this - bignum(other); }
    template<typename T>
    bignum& operator*=(T other) { return *this = *this * bignum(other); }
    template<typename T>
    bignum& operator/=(T other) { return *this = *this / bignum(other); }
    template<typename T>
    bignum& operator%=(T other) { return *this = *this % bignum(other); }
    bignum& operator+=(const char* other) { return *this = *this + bignum(other); }
    bignum& operator-=(const char* other) { return *this = *this - bignum(other); }
    bignum& operator*=(const char* other) { return *this = *this * bignum(other); }
    bignum& operator/=(const char* other) { return *this = *this / bignum(other); }
    bignum& operator%=(const char* other) { return *this = *this % bignum(other); }
    bignum& operator+=(const string& other) { return *this = *this + bignum(other); }
    bignum& operator-=(const string& other) { return *this = *this - bignum(other); }
    bignum& operator*=(const string& other) { return *this = *this * bignum(other); }
    bignum& operator/=(const string& other) { return *this = *this / bignum(other); }
    bignum& operator%=(const string& other) { return *this = *this % bignum(other); }
    bignum operator<<(int n) const { return *this * bignum(2).pow(n); }
    bignum operator>>(int n) const { return *this / bignum(2).pow(n); }
    bignum abs() const {
        bignum result = *this;
        result.isnegative = false;
        return result;
    }
    bool isEven() const { return (digits[0] % 2) == 0; }
    bool isOdd() const { return !isEven(); }
    bool isPrime() const {
        if (*this <= bignum(1)) return false;
        if (*this == bignum(2) || *this == bignum(3)) return true;
        if (isEven() || *this % bignum(3) == bignum(0)) return false;
        bignum i(5);
        bignum limit = sqrt();
        while (i <= limit) {
            if (*this % i == bignum(0) || *this % (i + bignum(2)) == bignum(0))return false;
            i += bignum(6);
        }
        return true;
    }
    bignum sqrt() const {
        if (isnegative) throw "Square root of negative number";
        if (*this == bignum(0) || *this == bignum(1)) return *this;
        bignum left(1), right = *this / bignum(2) + bignum(1);
        bignum result, mid;
        while (left <= right) {
            mid = (left + right) / bignum(2);
            bignum square = mid * mid;
            if (square == *this) return mid;
            if (square < *this) {
                left = mid + bignum(1);
                result = mid;
            } else {
                right = mid - bignum(1);
            }
        }
        return result;
    }
    bignum pow(int exponent) const {
        if (exponent < 0) throw "Negative exponent not supported";
        if (exponent == 0) return bignum(1);
        bignum result(1);
        bignum base = *this;
        while (exponent > 0) {
            if (exponent & 1) {
                result = result * base;
            }
            base = base * base;
            exponent >>= 1;
        }
        return result;
    }
    
    bignum powmod(int exponent, const bignum& mod) const {
        if (exponent < 0) throw "Negative exponent not supported";
        if (mod == bignum(0)) throw "Modulus cannot be zero";
        bignum result(1);
        bignum base = *this % mod;
        while (exponent > 0) {
            if (exponent & 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exponent >>= 1;
        }
        return result;
    }
    static bignum factorial(int n) {
        if (n < 0) throw "Factorial of negative number";
        if (n == 0 || n == 1) return bignum(1);
        bignum result(1);
        for (int i = 2; i <= n; i++) result *= i;
        return result;
    }
    int operator[](int pos) const {
        if (pos < 0) return 0;
        int block = pos / BASE_DIGITS;
        int position_in_block = pos % BASE_DIGITS;
        if (block >= length) return 0;
        int power = 1;
        for (int i = 0; i < position_in_block; i++) {
            power *= 10;
        }
        return (digits[block] / power) % 10;
    }
    int size() const {
        if (length == 1 && digits[0] == 0) return 1;
        int top_digits = 0;
        int temp = digits[length - 1];
        while (temp > 0) {
            top_digits++;
            temp /= 10;
        }
        return (length - 1) * BASE_DIGITS + top_digits;
    }
    bool canConvertToLongLong() const {
        static const long long MAX_SAFE = 9007199254740991LL;
        return *this >= bignum(-MAX_SAFE) && *this <= bignum(MAX_SAFE);
    }
    long long toLongLong() const {
        if (!canConvertToLongLong()) throw "Value too large for long long";
        long long result = 0;
        long long multiplier = 1;
        for (int i = 0; i < length; i++) {
            result += (long long)digits[i] * multiplier;
            multiplier *= BASE;
        }
        if (isnegative) result = -result;
        return result;
    }
    bool canConvertToInt() const {
        return *this >= bignum(-2147483648LL) && *this <= bignum(2147483647LL);
    }
    int toInt() const {
        if (!canConvertToInt()) throw "Value too large for int";
        return (int)toLongLong();
    }
    static bignum zero() { return bignum(0); }
    static bignum one() { return bignum(1); }
    static bignum ten() { return bignum(10); }
    static bignum maxValue() {
        bignum result;
        result.length = MAX_DIGITS;
        for (int i = 0; i < MAX_DIGITS; i++) {
            result.digits[i] = BASE - 1;
        }
        result.normalize();
        return result;
    }
    static void help() {
        printf("=== bignum 大整数类使用说明 ===\n");
        printf("1. 构造函数和赋值:\n");
        printf("   bignum a;                    // 默认构造函数，值为0\n");
        printf("   bignum b(12345);             // 从整数构造\n");
        printf("   bignum c(\"1234567890\");      // 从字符串构造\n");
        printf("   bignum d = \"9876543210\";     // 从C字符串构造\n");
        printf("   a = 100;                     // 赋值操作\n");
        printf("   a = \"9999999999\";            // 从字符串赋值\n");
        printf("\n");
        printf("2. 输入输出:\n");
        printf("   a.readnum();                 // 快速读取（跳过空白字符）\n");
        printf("   cout << a;                   // 输出到ostream\n");
        printf("   a.print();                   // 直接打印到stdout\n");
        printf("   string s = a.toString();     // 转换为字符串\n");
        printf("   char* str = a.toCStr();      // 转换为C字符串（需手动释放，不建议）\n");
        printf("\n");
        printf("3. 算术运算:\n");
        printf("   a + b, a - b, a * b, a / b, a %% b\n");
        printf("   -a                           // 取负\n");
        printf("   ++a, a++, --a, a--           // 自增自减\n");
        printf("   a += b, a -= b, a *= b, a /= b, a %%= b\n");
        printf("   a << n, a >> n               // 位运算模拟（乘以/除以2的n次方）\n");
        printf("\n");
        printf("4. 比较运算:\n");
        printf("   a == b, a != b, a < b, a <= b, a > b, a >= b\n");
        printf("\n");
        printf("5. 数学函数:\n");
        printf("   a.abs()                      // 绝对值\n");
        printf("   a.isEven(), a.isOdd()        // 奇偶判断\n");
        printf("   a.isPrime()                  // 质数判断（使用6n±1优化）\n");
        printf("   a.sqrt()                     // 平方根（整数部分）\n");
        printf("   a.pow(n)                     // 幂运算（快速幂算法）\n");
        printf("   a.powmod(n, m)               // 模幂运算（快速模幂）\n");
        printf("   bignum::factorial(n)         // 阶乘计算\n");
        printf("\n");
        printf("6. 属性和转换:\n");
        printf("   a.size()                     // 十进制位数\n");
        printf("   a[i]                         // 访问第i位数字（0为个位）\n");
        printf("   a.canConvertToInt()          // 检查是否可以转换为int\n");
        printf("   a.toInt()                    // 转换为int（可能抛出异常）\n");
        printf("   a.canConvertToLongLong()     // 检查是否可以转换为long long\n");
        printf("   a.toLongLong()               // 转换为long long（可能抛出异常）\n");
        printf("\n");
        printf("7. 静态常量:\n");
        printf("   bignum::zero()               // 返回0\n");
        printf("   bignum::one()                // 返回1\n");
        printf("   bignum::ten()                // 返回10\n");
        printf("   bignum::maxValue()           // 返回最大可能值\n");
        printf("\n");
        printf("8. 混合类型运算:\n");
        printf("   支持与int, long long, string, const char*的混合运算\n");
        printf("   示例: a + 100, 50 + a, a + \"123\", \"456\" * a\n");
        printf("\n");
        printf("9. 性能特点:\n");
        printf("   - 使用万进制（每4位一组）存储，提高运算效率\n");
        printf("   - 幂运算使用快速幂算法（O(log n)复杂度）\n");
        printf("   - 质数判断使用6n±1优化算法\n");
        printf("   - 避免使用三目运算符，提高竞赛环境性能\n");
        printf("   - 支持大数运算（最大%d位十进制数）\n", MAX_DIGITS * 4);
        printf("\n");
        printf("10. 异常处理:\n");
        printf("   除零操作和负数平方根会抛出字符串异常\n");
        printf("   类型转换超出范围会抛出异常\n");
        printf("   使用try-catch捕获异常:\n");
        printf("   try { a / bignum(0); } catch (const char* e) { /* 处理异常 */ }\n");
        printf("\n");
        printf("11. 限制说明:\n");
        printf("   以下操作不会实现（因为C++标准库已定义这些操作）:\n");
        printf("   \"123\" * \"123\"                // 字符串乘法（未定义）\n");
        printf("   \"123\" + \"123\"                // 字符串连接（已定义）\n");
        printf("   string(\"123\") * string(\"123\") // 字符串乘法（未定义）\n");
        printf("   string(\"123\") + string(\"123\") // 字符串连接（已定义）\n");
        printf("   正确做法：先转换为bignum对象再运算\n");
        printf("   示例：bignum(\"123\") * bignum(\"123\")\n");
    }
    friend istream& operator>>(istream& is, bignum& num) {
        string str;
        is >> str;
        num = bignum(str);
        return is;
    }
    friend ostream& operator<<(ostream& os, const bignum& num) {
        os << num.toString();
        return os;
    }
};
const int bignum::MAX_DIGITS = 1005;
const int bignum::BASE = 10000;
const int bignum::BASE_DIGITS = 4;
int main(){
    bignum a,b;
    a.readnum();
    b.readnum();
    bignum c=a+b;
    c.print();
}