3. 普及组算法部分 - high accuracy高精度 - 《信息学奥赛21天突破》

概念
高精度加法
- 大整数加法">例题：大整数加法
高精度减法
- 大整数减法">例题：大整数减法
高精度乘低精度
- 计算2的N次方">例题：计算2的N次方
高精度乘高精度
- 大整数乘法">例题：大整数乘法
高精度除低精度
- 除以13">例题：除以13
高精度除高精度
《一本通》题目
参考文献

概念

当学完C++语言部分的知识后，可以学习一下高精度习题，锻炼一下自己对一维数组的理解，提高自己的代码能力。相信我，如果你不是抄代码的，你将写得怀疑人生。（这个地方写的时候，真的挺容易写错）

主要的思想是利用竖式加减乘除的原理，进行模拟。这块一般是背模板理解，有用string读入转vector的，有直接用一维数组处理的。在理解原理上，vector的模板好理解。在实际使用中，一维数组的使用更加常见。

现在的考试基本不单纯考高精度，很早之前省选有一次考的高精除法，结果只有很少人写对，然而题目区分度却被diss。现在都基本开LL过部分分，或者会取模，避免高精。普及组里如果遇到高精度，可能现场也不太会写高精，需要比较强的代码能力。

高精度加法

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

//一维数组版本
void add(int A[], int B[], int C[])
{
    int t = 0;
    for (int i = 0; i <= lena || i <= lenb; i++)
    {
        if (i <= lena) t += A[i];
        if (i <= lenb) t += B[i];
        C[lenc++] = t % 10;
        t /= 10;
    }
    if (t) C[lenc] = 1;
    while (lenc > 0 && C[lenc] == 0) lenc--;
    for (int i = lenc; i >= 0; i--) cout << C[i];
    puts("");
}

例题：大整数加法

高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 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;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//一维数组版本
void add(int A[], int B[], int C[])
{
    int t = 0;
    for (int i = 0; i < lena; i++)
    {
        t = A[i] - t;
        if (i < lenb) t -= B[i];
        C[lenc++] = (t + 10) % 10;
        if (t < 0) t = 1;
        else t = 0;
    }
    while (lenc > 0 && C[lenc] == 0) lenc--;
}

例题：大整数减法

高精度乘低精度

//string版本
// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int 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;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//一维数组版本
void mul(int A[], int x)
{
    int t = 0;
    for (int i = 0; i < len; i++)
    {
        A[i] = A[i] * x + t;
        if (A[i] >= 10) t = 1;
        else t = 0;
        A[i] %= 10;
    }
    if (t) A[len++] = 1;
}

例题：计算2的N次方

高精度乘高精度

vector<int> mul(vector<int> A, vector<int> B)
{
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i ++ )
        for (int j = 0; j < B.size(); j ++ )
            C[i + j] += A[i] * B[j];
    for (int i = 0, t = 0; i < C.size() || t; i ++ )
    {
        t += C[i];
        if (i >= C.size()) C.push_back(t % 10);
        else C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && !C.back()) C.pop_back();
    return C;
}

//一维数组版本
    for (int i = a.size()- 1; i >= 0; i--) A[lena++] = a[i] - '0';
    for (int i = b.size()- 1; i >= 0; i--) B[lenb++] = b[i] - '0';
    for (int i = 0; i < lena; i++)
        for (int j = 0; j < lenb; j++)
            C[i + j] += A[i] * B[j];
    for (int i = 0; i < lena + lenb; i++)
    {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }
    int lenc = lena + lenb;
    while (lenc > 0 && C[lenc] == 0) lenc--;
    for (int i = lenc; i >= 0; i--) cout << C[i];
    puts("");

例题：大整数乘法

高精度除低精度

//string版本
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &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());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

//一维数组版本
    for (int i = 0, len = a.size(); i < len; i++) A[lena++] = a[i] - '0';
    int t = 0;
    for (int i = 0; i < lena; i++)
    {
        C[i] =  (t * 10 + A[i]) / B;
        t = (t * 10 + A[i]) % B;
    }
    while (lenc < lena && C[lenc] == 0) lenc++;
    if (lenc == lena) lenc--;
    for (int i = lenc; i < lena; i++) cout << C[i];
    puts("");