高精度

支持高位数的运算系统.

简介 #

高精度是支持高位数的运算系统. 本章仅介绍最常用的正整数运算系统.

构造 #

在 vector<int> 容器内保存每位数字，并实现自动处理进位.

vector<int> 的位数要从 $0$ 记起（第 $0$ 位，第 $1$ 位，$\cdots$）.

struct Wint:vector<int> {   // 以 vector 为基类
    Wint(int n = 0) {   // 初始化为 0
        push_back(n);
        upgrade();
    }
    Wint& upgrade() {   // 处理进位
        while (!empty() && !back())
            pop_back(); // 去除最高位多余的 0
        if (empty())
            return *this;

        for (int i = 1; i < size(); i ++) { // 满 10 进 1
            (*this)[i] += (*this)[i - 1] / 10;
            (*this)[i - 1] %= 10;
        }
        while (back() >= 10) {  // 最高位 >= 10 时，新增一位
            push_back(back() / 10);
            (*this)[size() - 2] %= 10;
        }
        return *this;
    }
};

输入 #

取出字符串的每一位，倒序存入数组.

Wint init(string s) {
    Wint n;
    for (int i = s.size() - 1; i >= 0; i --)
        n.push_back(s[i] - '0');
    return n;
}

输出 #

数据是倒序储存的，故倒序输出.

void print(Wint n) {
    if (n.empty()) printf("0");
    for (int i = n.size() - 1; i >= 0; i --)
        printf("%d", n[i]);
}

比较 #

先比较位数. 若位数相同，则从高位到低位逐位比较.

bool operator != (const Wint &a, const Wint &b) {
    if (a.size() != b.size())
        return true;
    for (int i = a.size() - 1; i >= 0; i --)
        if (a[i] != b[i])
            return true;
    return false;
}

bool operator == (const Wint &a, const Wint &b) {
    return !(a != b);
}

bool operator < (const Wint &a, const Wint &b) {
    if (a.size() != b.size())
        return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; i --)
        if (a[i] != b[i])
            return a[i] < b[i];
    return false;
}

bool operator > (const Wint &a, const Wint &b) {
    return b < a;
}

bool operator <= (const Wint &a, const Wint &b) {
    return !(a > b);
}

bool operator >= (const Wint &a, const Wint &b) {
    return !(a < b);
}

加法 #

从低位到高位，将两数对应位置相加.

先实现 += 方法，节省传参时间.

Wint& operator += (Wint &a, const Wint &b) {
    if (a.size() < b.size())
        a.resize(b.size());
    for (int i = 0; i < b.size(); i ++)
        a[i] += b[i];
    return a.upgrade();
}

Wint operator + (Wint a, const Wint &b) {
    return a += b;
}

减法 #

返回差的绝对值. 从低位到高位，将两数对应位置相减. 不够减要借位.

Wint& operator -= (Wint &a, Wint b) {
    if (a < b) swap(a,b);
    for (int i = 0; i < b.size(); i ++) {
        if (a[i] < b[i]) {  // 需要借位
            a[i + 1] --;
            a[i] += 10;
        }
        a[i] -= b[i];
    }
    return a.upgrade();
}

Wint operator - (Wint a, const Wint &b) {
    return a -= b;
}

乘法 #

将 $a$ 的第 $i$ 位乘 $b$ 的第 $j$ 位累加在答案的第 $i+j$ 位上.

Wint operator * (const Wint &a, const Wint &b) {
    Wint n;
    n.assign(a.size( ) + b.size() - 1, 0);
    for (int i = 0; i < a.size(); i ++)
        for (int j = 0; j < b.size(); j ++)
            n[i + j] += a[i] * b[j];
    return n.upgrade();
}

Wint& operator *= (Wint &a, const Wint &b) {
    return a = a * b;
}

除法 #

先实现带余除法函数，再重载符号方法.

将 $b$ 和 $a$ 最高位对齐，重复相减，统计减的次数.

Wint divmod(Wint &a, const Wint &b) {
    Wint ans;
    for (int t = a.size() - b.size(); a >= b; t --) {
        Wint d;
        d.assign(t + 1, 0);
        d.back() = 1;
        Wint c = b * d;
        while (a >= c) {
            a -= c;
            ans += d;
        }
    }
    return ans;
}

Wint operator / (Wint a, const Wint &b) {
    return divmod(a, b);
}

Wint& operator /= (Wint &a, const Wint &b) {
    return a = a / b;
}

Wint& operator %= (Wint &a, const Wint &b) {
    divmod(a, b);
    return a;
}

Wint operator % (Wint a, const Wint &b) {
    return a %= b;
}