GabWiki

Appearance

高精度 ​

高精度加法 ​

高精度自然数 + 高精度自然数： ​

C++
// 高精度整数均以vector倒序存储
vector<int> add(const vector<int>& a, const vector<int>& b) {
    const int n = a.size(), m = b.size(), len = max(n, m) + 1;
    vector<int> c(len);
    for (int i = 0, rem = 0; i < len || rem; ++i) {
        if (i < n) rem += a[i];
        if (i < m) rem += b[i];
        c[i] = rem % 10;
        rem /= 10;
    }
    if (c.back() == 0) c.pop_back();
    return c;
}
// 高精度整数均以vector倒序存储
vector<int> add(const vector<int>& a, const vector<int>& b) {
    const int n = a.size(), m = b.size(), len = max(n, m) + 1;
    vector<int> c(len);
    for (int i = 0, rem = 0; i < len || rem; ++i) {
        if (i < n) rem += a[i];
        if (i < m) rem += b[i];
        c[i] = rem % 10;
        rem /= 10;
    }
    if (c.back() == 0) c.pop_back();
    return c;
}

高精度减法 ​

高精度自然数 − 高精度自然数 ​

C++
// 高精度整数均以vector倒序存储
vector<int> sub(const vector<int>& a, const vector<int>& b, bool neg = false) {
    if (cmp(a, b)) return sub(b, a, true);
    vector<int> c(a.size());
    for (int i = 0, rem = 0; i < a.size(); ++i) {
        rem += a[i];
        if (i < b.size()) rem -= b[i];
        c[i] = (rem + 10) % 10;
        rem = -(rem < 0);
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    if (neg) c.back() = -c.back();
    return c;
}
// 高精度整数均以vector倒序存储
vector<int> sub(const vector<int>& a, const vector<int>& b, bool neg = false) {
    if (cmp(a, b)) return sub(b, a, true);
    vector<int> c(a.size());
    for (int i = 0, rem = 0; i < a.size(); ++i) {
        rem += a[i];
        if (i < b.size()) rem -= b[i];
        c[i] = (rem + 10) % 10;
        rem = -(rem < 0);
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    if (neg) c.back() = -c.back();
    return c;
}

高精度乘法 ​

高精度自然数 × 低精度自然数 ​

C++
// 高精度整数均以vector倒序存储
vector<int> mul(const vector<int>& a, const int& b) {
    const int n = a.size();
    int t = b, m = 0;
    while (t) ++m, t /= 10;
    int len = n + m + 1;
    vector<int> c(len);
    for (int i = 0, rem = 0; i < len || rem; ++i) {
        if (i < n) rem += a[i] * b;
        c[i] = rem % 10;
        rem /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
// 高精度整数均以vector倒序存储
vector<int> mul(const vector<int>& a, const int& b) {
    const int n = a.size();
    int t = b, m = 0;
    while (t) ++m, t /= 10;
    int len = n + m + 1;
    vector<int> c(len);
    for (int i = 0, rem = 0; i < len || rem; ++i) {
        if (i < n) rem += a[i] * b;
        c[i] = rem % 10;
        rem /= 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

高精度除法 ​

高精度自然数 ÷ 低精度自然数 ​

C++
// 高精度整数均以vector倒序存储
vector<int> div(const vector<int>& a, const int& b, int& rem) {
    const int n = a.size();
    vector<int> c(n);
    rem = 0;
    for (int i = n - 1; i >= 0; --i) {
        rem = rem * 10 + a[i];
        c[n - i - 1] = rem / b;
        rem %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}
// 高精度整数均以vector倒序存储
vector<int> div(const vector<int>& a, const int& b, int& rem) {
    const int n = a.size();
    vector<int> c(n);
    rem = 0;
    for (int i = n - 1; i >= 0; --i) {
        rem = rem * 10 + a[i];
        c[n - i - 1] = rem / b;
        rem %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}