高精度保姆级教学！

· · 算法·理论

引入

小董在解决 A + B problem 时发现 a 与 b 的数据范围远远超过 int128 ，那这个怎么办呢？

解决

小董刚刚上完模拟课，于是有了一个大胆的想法：既然系统自带的加号不行，那我自己写总可以了吧！

这个方法便是高精度。

那么如何实现呢？很简单，模拟加法竖式。

考虑从个位将两个数逐位相加。此时我们发现有的位上的数之和成了两位数。那就遵循加法竖式的原则，向下一位进位即可。

#include <bits/stdc++.h>
using namespace std;
int a[105], b[105], ans[105];
int main()
{
    string str1, str2;
    cin >> str1 >> str2;
    for (int i = str1.length() - 1; i >= 0; i--)
    {
        a[str1.length() - i] = str1[i] - '0';
    }
    for (int i = str2.length() - 1; i >= 0; i--)
    {
        b[str2.length() - i] = str2[i] - '0';
    }
    for (int i = 1; i <= max(str1.length(), str2.length()) + 1; i++)
    {
        ans[i] += a[i] + b[i];
        if (ans[i] >= 10)
        {
            ans[i] -= 10;
            ans[i + 1]++;
        }
    }
    bool flg = false;
    for (int i = max(str1.length(), str2.length()) + 1; i >= 1; i--)
    {
        if (ans[i] != 0)
            flg = true;
        if (flg)
            cout << ans[i];
    }
}

继续继续！小董已经求知若渴了！

同理同理，我们也可以写出减法！

同样，代码并不长，也很好理解。

#include <bits/stdc++.h>
using namespace std;
int a[105], b[105], ans[105];
int main()
{
    string str1, str2;
    cin >> str1 >> str2;
    for (int i = str1.length() - 1; i >= 0; i--)
    {
        a[str1.length() - i] = str1[i] - '0';
    }
    for (int i = str2.length() - 1; i >= 0; i--)
    {
        b[str2.length() - i] = str2[i] - '0';
    }
    for (int i = 1; i <= max(str1.length(), str2.length()) + 1; i++)
    {
        ans[i] += a[i] - b[i];
        if (ans[i] < 0)
        {
            ans[i] += 10;
            ans[i + 1]--;
        }
    }
    bool flg = false;
    for (int i = max(str1.length(), str2.length()) + 1; i >= 1; i--)
    {
        if (ans[i] != 0)
            flg = true;
        if (flg)
            cout << ans[i];
    }
}

推广

小董寻思着，要是乘法的数据范围也很大呢？于是，聪明的他又想到了高精度！

与刚才同样的原理，运用乘法竖式去模拟。这个就比较复杂了，建议各位同学自己去画一下多体会一下。

以上就是全部要点了，更多细节请同学们看代码体会 （码风较丑，见谅）。

#include <bits/stdc++.h>
using namespace std;
int a[105], b[105];
int ans[505], ccc[505];
char c[105], d[105];
signed main()
{
    cin >> c + 1 >> d + 1;
    int lenc = strlen(c + 1);
    int lend = strlen(d + 1);
    for (int i = 1; i <= lenc; i++)
    {
        a[i] = c[lenc - i + 1] - '0';
    }
    for (int i = 1; i <= lend; i++)
    {
        b[i] = d[lend - i + 1] - '0';
    }
    for (int i = 1; i <= lend; i++)
    {
        int pos = i - 1;
        memset(ccc, 0, sizeof ccc);
        for (int j = 1; j <= lenc; j++)
        {
            int tmp = a[j] * b[i] + ccc[j];
            ccc[j] = tmp % 10;
            ccc[j + 1] = tmp / 10;
        }
        for (int k = 1 + pos; k <= max(lenc, lend) + 1 + pos; k++)
        {
            ans[k] += ccc[k - pos];
        }
    }
    for (int i = 1; i <= 503; i++)
    {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
    bool flg = false;
    for (int i = 504; i >= 1; i--)
    {
        if (ans[i] != 0 && !flg)
            flg = true;
        if (flg)
            cout << ans[i];
    }
}

进阶

聪明的小董再次想到，有了乘法怎么能把除法落了呢？！

除法个人认为要比乘法简单些，直接看代码吧，有很多都是同学们看到前两部分后就能推出来的，希望同学们多多思考一下。

以下这份代码是求出 \lfloor a \div b \rfloor 与 a \bmod b 的。 

#include <bits/stdc++.h>
using namespace std;
int lt;
int a[105], b;
int k[105];
int main()
{
    char c[105];
    cin >> c + 1;
    int lenc = strlen(c + 1);
    for (int i = 1; i <= lenc; i++)
    {
        a[i] = c[i] - '0';
    }
    cin >> b;
    int lena = lenc;
    int tmp = 0;
    for (int i = 1; i <= lena; i++)
    {
        tmp = tmp * 10 + a[i];
        k[i] = tmp / b;
        lt = tmp % b;
        tmp = lt;
    }
    bool flg = false;
    for (int i = 1; i <= lena; i++)
    {
        if (k[i] != 0 || flg)
        {
            cout << k[i];
            flg = true;
        }
    }
    if (!flg)
        cout << 0;
    cout << endl << lt << endl;
    return 0;
}

尾声

小董终于掌握了全部高精度的知识！

作者：zzx

求赞！