kizumi_header_banner_img

是先学算法，先刷题，还是先写日记呢？

加载中

POST
文章导读
基础算法 算法笔记

高精度

avatar
RonF02 2026年1月31日 42
0 评论

高精度一般可以直接用python解决。但此处为了以防特别恶心的超级超级高精连python的input都不够用而导致RE的高精，特写文章记录。最后会贴出完整的封装代码

*使用vector，没有压位，默认出现的数都是正的

存储

string s; cin >> s;
vector<int> array;
for (int i = s.size() - 1; i >= 0; i -- ) array.push_back(s[i] - '0');

借用字符串倒着存，a[0]存最低位，a[s.size() – 1]存最高位。便于有进位时使用push_back在最高位上进位。

去除前导零

while (A.size() > 1 && A.back() == 0) A.pop_back();

一行代码，无需多言。

高精加

vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(1);
    return C;
}

每一位如果存在，则存入临时变量t中。则t的个位就是这一位的答案，t的十位就是进位的数。

高精减

先判断两个vector类型的大整数的大小

bool operator >= (const unsignedBigInt &B)
{
    if (this->array.size() != B.array.size()) //长度不同长的更长
        return this->array.size() > B.array.size();
    
    for (int i = this->array.size() - 1; i >= 0; i -- )//长度相同，每一位比较
    {
        if (this->array[i] != B.array[i]) 
        {
            return this->array[i] > B.array[i];
        }
    }
    return 1;
}

在高精减法中，默认被减数大于减数

vector<int> sub(vector<int> &A, vector<int> &B) // 默认A>=B
{
    vector<int> C;
    
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    this->removeLeadingZero(C);
    return C;
}

核心算法为t = A[i] – B[i] – t ，即被减数的这一位减去减数的这一位，再减去借位的数。如果剩下的是非负的，说明没借位，重置为0。否则重置为1。

以防二者高位相同，需要去除前导零。

高精乘低精

vector<int> mul(vector<int> &A, ll b)
{
    vector<int> C;
    ll t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    this->removeLeadingZero(C);
    return C;
}

可类比高精加法。不同点在于，高精乘的进位可能是两位数，需要继续处理。‘
以防乘数有零，可以用特判或者去除前导零的方法。

思路：1234*78 = 4*78 + 30*78 + 200 * 78 + 1000 * 78

4 * 78 = 312，进位31，个位写2
3 * 78 = 234，个位在31的基础上加4，个位35，写5，进位为23 + 3 = 26
2 * 78 = 156，个位在26的基础上加6，个位32，写2，进位为15 + 3 = 18
1 * 78 = 78 ，个位在18的基础上加8，个位26，写6，进位为7 + 2 = 9
进位的9直接写
最终答案为96252，经过计算器验证正确，此处不做证明。
更加详细的高精乘高精可参考高精度乘法从入门到入土 – 洛谷专栏

高精带余数除以低精度

vector<int> div(vector<int> &A, ll &b, ll &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    this->removeLeadingZero(C);
    return C;
}

模拟竖式除法。其中落下来下一位用 r = r * 10 + A[i] 计算
因为要一般化输出所以要reverse一下答案的数组
去除前导零也是必须的

完整代码（已封装）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class unsignedBigInt
{
    private:
        vector<int> array;
        ll r;

        void removeLeadingZero(vector<int> &A)
        {
            while (A.size() > 1 && A.back() == 0) A.pop_back();
        }

        bool operator >= (const unsignedBigInt &B)
        {
            if (this->array.size() != B.array.size()) 
                return this->array.size() > B.array.size();
            
            for (int i = this->array.size() - 1; i >= 0; i -- )
            {
                if (this->array[i] != B.array[i]) 
                {
                    return this->array[i] > B.array[i];
                }
            }
            return 1;
        }

        vector<int> add(vector<int> &A, vector<int> &B)
        {
            vector<int> C;
            
            int t = 0;
            for (int i = 0; i < A.size() || i < B.size(); i ++ )
            {
                if (i < A.size()) t += A[i];
                if (i < B.size()) t += B[i];
                C.push_back(t % 10);
                t /= 10;
            }
            if (t) C.push_back(1);
            return C;
        }

        vector<int> sub(vector<int> &A, vector<int> &B) // 默认A>=B
        {
            vector<int> C;
            
            int t = 0;
            for (int i = 0; i < A.size(); i ++ )
            {
                t = A[i] - t;
                if (i < B.size()) t -= B[i];
                C.push_back((t + 10) % 10);
                if (t < 0) t = 1;
                else t = 0;
            }
            this->removeLeadingZero(C);
            return C;
        }

        vector<int> mul(vector<int> &A, ll b)
        {
            vector<int> C;
            ll t = 0;
            for (int i = 0; i < A.size() || t; i ++ )
            {
                if (i < A.size()) t += A[i] * b;
                C.push_back(t % 10);
                t /= 10;
            }
            this->removeLeadingZero(C);
            return C;
        }

        vector<int> div(vector<int> &A, ll &b, ll &r)
        {
            vector<int> C;
            r = 0;
            for (int i = A.size() - 1; i >= 0; i -- )
            {
                r = r * 10 + A[i];
                C.push_back(r / b);
                r %= b;
            }
            reverse(C.begin(), C.end());
            this->removeLeadingZero(C);
            return C;
        }

    public:
        unsignedBigInt(string s = "")
        {
            for (int i = s.size() - 1; i >= 0; i -- ) array.push_back(s[i] - '0');
        }

        void output()
        {
            for (int i = this->array.size() - 1; i >= 0; i --) cout << this->array[i];
            cout << '\n';
        }

        unsignedBigInt operator + (unsignedBigInt &B)
        {
            unsignedBigInt C;
            C.array = this->add(this->array, B.array);
            return C;
        }

        unsignedBigInt operator - (unsignedBigInt &B)
        {
            unsignedBigInt C;
            if (*this >= B)
            {
                C.array = this->sub(this->array, B.array);
            }
            else 
            {
                C.array = this->sub(B.array, this->array);
                C.array[C.array.size() - 1] *= -1;
            }
            return C;
        }

        unsignedBigInt operator * (ll &B)
        {
            unsignedBigInt C;
            C.array = this->mul(this->array, B);
            return C;
        }

        unsignedBigInt operator / (ll &B)
        {
           unsignedBigInt C;
           C.array = this->div(this->array, B, this->r);
           return C; 
        }

        ll operator % (ll &B)
        {
            this->div(this->array, B, this->r);
            return this->r;
        }
};

为了学习一下C++的类怎么使用，封装了一下高精度的常用功能
（其实是y总就交了这些，别的更牛×的还不会）

评论（0）

查看评论列表

暂无评论

发表评论

表情 颜文字
插入代码
RonF02的博客

搜索

归档

个人信息

avatar

24
文章
2
评论
1
用户