高精度模板

一、33DAI 写的简易粗糙低效率模板

const int MAXLEN = 50000;
struct Num
{
    int sign;
    int len;
    int d[MAXLEN]; // d[0]~d[len-1]
    // 默认的构造函数（传入长度）
    Num(int x = 0)
    {
        sign = 1, len = x;
        for (int i = 0; i < len; i++)
            d[i] = 0;
    }
    // 基于一个非负整数字符串构造一个高精度的数
    Num(const string &s)
    {
        sign = 1;
        if (s[0] == '-')
            sign = -1;
        int pos = 0; // 第一个非零位
        while (pos <= (int)s.size() - 2 &&
                （s[pos] == '-' || s[pos] == '0'))
            pos++;
        len = ((int)s.size() - 1) - (pos) + 1;
        for (int i = 0; i <= len - 1; i++)
            d[i] = s[(int)s.size() - 1 - i] - '0';
    }
    void zero()
    {
        while (len > 1 && d[len - 1] == 0)
            len--;
        if (len == 1 && d[0] == 0)
            sign = 1;
    }
    void jin()
    {
        // 除了最高位之外的进位
        for (int i = 0; i <= len - 2; i++)
        {
            d[i + 1] += d[i] / 10;
            d[i] %= 10;
        }
        // 最高位的进位
        while (d[len - 1] >= 10)
        {
            d[len] = d[len - 1] / 10;
            d[len - 1] %= 10;
            len++;
        }
    }
    Num operator-() const
    {
        Num c = *this;
        c.sign = -c.sign;
        return c;
    }
    void write() const
    {
        if (sign == -1)
            cout << "-";
        for (int i = len - 1; i >= 0; i--)
            cout << d[i];
        cout << "\n";
    }
    Num operator+(const Num &other) const
    {
        if (sign == 1 && other.sign == -1)
            return (*this - (-other));
        if (sign == -1 && other.sign == 1)
            return (other - (-*this));
        if (sign == -1 && other.sign == -1)
            return (*this - (-other));
        Num z;
        z.len = max(len, other.len);
        // 相加
        for (int i = 0; i < z.len; i++)
        {
            if (len >= i + 1 && other.len >= i + 1)
                z.d[i] = d[i] + other.d[i];
            else if (len >= i + 1)
                z.d[i] = d[i];
            else
                z.d[i] = other.d[i];
        }
        z.jin();
        return z;
    }
    bool operator<(const Num &other) const
    {
        if (sign != other.sign)
            return sign == -1;
        if (len != other.len)
        {
            if (sign == -1)
                return other.len < len;
            return len < other.len;
        }
        for (int i = len - 1; i >= 0; i--)
            if (d[i] != other.d[i])
            {
                if (sign == -1)
                    return other.d[i] < d[i];
                return d[i] < other.d[i];
            }
        return false;
    }
    Num operator-(const Num &other) const
    {
        if (sign == 1 && other.sign == -1)
            return (*this + (-other));
        if (sign == -1 && other.sign == 1)
            return -(-*this + other);
        if (sign == -1 && other.sign == -1)
            return *this + (-other);
        Num z = *this;
        if (z < other)
            return -(other - z);
        for (int i = 0; i < other.len; i++)
            z.d[i] -= other.d[i];
        for (int i = 0; i < z.len; i++)
            if (z.d[i] < 0)
                z.d[i + 1]--, z.d[i] += 10;
        z.zero();
        return z;
    }
    Num operator*(int other) const
    {
        Num z = *this;
        if (other < 0)
        {
            z.sign = -z.sign;
            other = -other;
        }
        for (int i = 0; i < z.len; i++)
            z.d[i] *= other;
        z.jin();
        z.zero();
        return z;
    }
    Num operator*(const Num &other) const
    {
        Num z(len + other.len - 1);
        z.sign = sign * other.sign;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < other.len; j++)
                z.d[i + j] += d[i] * other.d[j];
        z.jin();
        z.zero();
        return z;
    }
    Num operator/(int other) const
    {
        Num z(len);
        z.sign = sign;
        if (other < 0)
        {
            other = -other;
            z.sign *= -1;
        }
        int r = 0;
        for (int i = len - 1; i >= 0; i--)
        {
            z.d[i] = (r * 10 + d[i]) / other;
            r = (r * 10 + d[i]) % other;
        }
        z.zero();
        return z;
    }
    int operator%(int other) const
    {
        if (other < 0)
            other = -other;
        int r = 0;
        for (int i = len - 1; i >= 0; i--)
            r = (r * 10 + d[i]) % other;
        return r * sign;
    }
};

二、BitIntTiny 模板

实现的内容：

• BigIntTiny a;：定义一个初始为 $0$ 的大整数
• BigIntTiny a = 33;：通过 int 初始化
• BigIntTiny a = s;：通过 string 初始化
• a.get_pos(pos)：获取第 pos 位的数位内容
• a.to_str()：得到对应的字符串，一般用来输出
• a = -a;：取反
• a < b、a == b：比较大小
• a + b、a - b、a * b、a / b、a % b：四则运算

因为定义了 int 对高精度的转换，所以加减乘除都能直接高精对低精运算。

struct BigIntTiny
{
    int sign;
    std::vector<int> v;

    BigIntTiny() : sign(1) {}
    BigIntTiny(const std::string &s) { *this = s; }
    BigIntTiny(int v)
    {
        char buf[21];
        sprintf(buf, "%d", v);
        *this = buf;
    }
    void zip(int unzip)
    {
        if (unzip == 0)
        {
            for (int i = 0; i < (int)v.size(); i++)
                v[i] = get_pos(i * 4) + get_pos(i * 4 + 1) * 10 + get_pos(i * 4 + 2) * 100 + get_pos(i * 4 + 3) * 1000;
        }
        else
            for (int i = (v.resize(v.size() * 4), (int)v.size() - 1), a; i >= 0; i--)
                a = (i % 4 >= 2) ? v[i / 4] / 100 : v[i / 4] % 100, v[i] = (i & 1) ? a / 10 : a % 10;
        setsign(1, 1);
    }
    int get_pos(unsigned pos) const { return pos >= v.size() ? 0 : v[pos]; }
    BigIntTiny &setsign(int newsign, int rev)
    {
        for (int i = (int)v.size() - 1; i > 0 && v[i] == 0; i--)
            v.erase(v.begin() + i);
        sign = (v.size() == 0 || (v.size() == 1 && v[0] == 0)) ? 1 : (rev ? newsign * sign : newsign);
        return *this;
    }
    std::string to_str() const
    {
        BigIntTiny b = *this;
        std::string s;
        for (int i = (b.zip(1), 0); i < (int)b.v.size(); ++i)
            s += char(*(b.v.rbegin() + i) + '0');
        return (sign < 0 ? "-" : "") + (s.empty() ? std::string("0") : s);
    }
    bool absless(const BigIntTiny &b) const
    {
        if (v.size() != b.v.size())
            return v.size() < b.v.size();
        for (int i = (int)v.size() - 1; i >= 0; i--)
            if (v[i] != b.v[i])
                return v[i] < b.v[i];
        return false;
    }
    BigIntTiny operator-() const
    {
        BigIntTiny c = *this;
        c.sign = (v.size() > 1 || v[0]) ? -c.sign : 1;
        return c;
    }
    BigIntTiny &operator=(const std::string &s)
    {
        if (s[0] == '-')
            *this = s.substr(1);
        else
        {
            for (int i = (v.clear(), 0); i < (int)s.size(); ++i)
                v.push_back(*(s.rbegin() + i) - '0');
            zip(0);
        }
        return setsign(s[0] == '-' ? -1 : 1, sign = 1);
    }
    bool operator<(const BigIntTiny &b) const
    {
        return sign != b.sign ? sign < b.sign : (sign == 1 ? absless(b) : b.absless(*this));
    }
    bool operator==(const BigIntTiny &b) const { return v == b.v && sign == b.sign; }
    BigIntTiny &operator+=(const BigIntTiny &b)
    {
        if (sign != b.sign)
            return *this = (*this) - -b;
        v.resize(std::max(v.size(), b.v.size()) + 1);
        for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++)
        {
            carry += v[i] + b.get_pos(i);
            v[i] = carry % 10000, carry /= 10000;
        }
        return setsign(sign, 0);
    }
    BigIntTiny operator+(const BigIntTiny &b) const
    {
        BigIntTiny c = *this;
        return c += b;
    }
    void add_mul(const BigIntTiny &b, int mul)
    {
        v.resize(std::max(v.size(), b.v.size()) + 2);
        for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++)
        {
            carry += v[i] + b.get_pos(i) * mul;
            v[i] = carry % 10000, carry /= 10000;
        }
    }
    BigIntTiny operator-(const BigIntTiny &b) const
    {
        if (sign != b.sign)
            return (*this) + -b;
        if (absless(b))
            return -(b - *this);
        BigIntTiny c;
        for (int i = 0, borrow = 0; i < (int)v.size(); i++)
        {
            borrow += v[i] - b.get_pos(i);
            c.v.push_back(borrow);
            c.v.back() -= 10000 * (borrow >>= 31);
        }
        return c.setsign(sign, 0);
    }
    BigIntTiny operator*(const BigIntTiny &b) const
    {
        if (b < *this)
            return b * *this;
        BigIntTiny c, d = b;
        for (int i = 0; i < (int)v.size(); i++, d.v.insert(d.v.begin(), 0))
            c.add_mul(d, v[i]);
        return c.setsign(sign * b.sign, 0);
    }
    BigIntTiny operator/(const BigIntTiny &b) const
    {
        BigIntTiny c, d;
        d.v.resize(v.size());
        double db = 1.0 / (b.v.back() + (b.get_pos((unsigned)b.v.size() - 2) / 1e4) +
                           (b.get_pos((unsigned)b.v.size() - 3) + 1) / 1e8);
        for (int i = (int)v.size() - 1; i >= 0; i--)
        {
            c.v.insert(c.v.begin(), v[i]);
            int m = (int)((c.get_pos((int)b.v.size()) * 10000 + c.get_pos((int)b.v.size() - 1)) * db);
            c = c - b * m, d.v[i] += m;
            while (!(c < b))
                c = c - b, d.v[i] += 1;
        }
        return d.setsign(sign * b.sign, 0);
    }
    BigIntTiny operator%(const BigIntTiny &b) const { return *this - *this / b * b; }
    bool operator>(const BigIntTiny &b) const { return b < *this; }
    bool operator<=(const BigIntTiny &b) const { return !(b < *this); }
    bool operator>=(const BigIntTiny &b) const { return !(*this < b); }
    bool operator!=(const BigIntTiny &b) const { return !(*this == b); }
};

例子

阶乘和

int main()
{
    int n;
    cin >> n;
    BigIntTiny sum = 0;
    BigIntTiny now = 1;
    for (int i = 1; i <= n; i++)
    {
        now = now * i;
        sum += now;
    }
    cout << sum.to_str();
    return 0;
}

高精度加法

string t;
BigIntTiny a, b;
int main()
{
    cin >> t; a = t;
    cin >> t; b = t;
    cout << (a + b).to_str();
    return 0;
}