高精度(一)：数组实现

前置知识

数组，模拟

目标

高精加高精，高精减高精，高精乘低精，高精乘高精，高精除低精，高精除高精

存储方式

高精度一般采用倒序存储。

例如 12345：

A[0] = 5
A[1] = 4
A[2] = 3
A[3] = 2
A[4] = 1

高精加高精

void add() {
    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++] = t;
}

高精减高精

要求 A >= B。

void sub() {
    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 > 1 && C[lenc - 1] == 0)
        lenc--;
}

高精乘低精

void mul(int b) {
    int t = 0;

    for (int i = 0; i < lena || t; i++) {
        if (i < lena) t += A[i] * b;

        C[lenc++] = t % 10;
        t /= 10;
    }

    while (lenc > 1 && C[lenc - 1] == 0)
        lenc--;
}

高精乘高精

void mul() {
    for (int i = 0; i < lena; i++)
        for (int j = 0; j < lenb; j++)
            C[i + j] += A[i] * B[j];

    lenc = lena + lenb;

    for (int i = 0; i < lenc; i++) {
        C[i + 1] += C[i] / 10;
        C[i] %= 10;
    }

    while (lenc > 1 && C[lenc - 1] == 0)
        lenc--;
}

高精除低精

计算：

A / b = C …… r

void div(int b, int &r) {
    r = 0;
    lenc = lena;

    for (int i = lena - 1; i >= 0; i--) {
        r = r * 10 + A[i];

        C[i] = r / b;
        r %= b;
    }

    while (lenc > 1 && C[lenc - 1] == 0)
        lenc--;
}

高精除高精

计算：

A / B = C

除数不能为 0。

int cmp(int X[], int lenx, int Y[], int leny) {
    if (lenx != leny)
        return lenx > leny ? 1 : -1;

    for (int i = lenx - 1; i >= 0; i--)
        if (X[i] != Y[i])
            return X[i] > Y[i] ? 1 : -1;

    return 0;
}


void sub(int X[], int &lenx, int Y[], int leny) {
    int t = 0;

    for (int i = 0; i < lenx; i++) {
        int x = X[i] - t;

        if (i < leny) x -= Y[i];

        X[i] = (x + 10) % 10;

        if (x < 0) t = 1;
        else t = 0;
    }

    while (lenx > 1 && X[lenx - 1] == 0)
        lenx--;
}


void div() {
    int R[N] = {};
    int lenr = 1;

    lenc = lena;

    for (int i = lena - 1; i >= 0; i--) {
        for (int j = lenr; j > 0; j--)
            R[j] = R[j - 1];

        R[0] = A[i];
        lenr++;

        while (lenr > 1 && R[lenr - 1] == 0)
            lenr--;

        while (cmp(R, lenr, B, lenb) >= 0) {
            sub(R, lenr, B, lenb);
            C[i]++;
        }
    }

    while (lenc > 1 && C[lenc - 1] == 0)
        lenc--;
}

总结

数组版本重点：

1. 倒序存储
2. 进位和借位
3. 除法从最高位开始计算
4. 高精除高精逐位试商