Introduction to Data Structures and algorithms

We all know that int can stand for -2147483648 to 2147483647, and long long can stand for -9223372036854775808 to 9223372036854775807, but what about bigger numbers? For example, the number has 100 digits, 1,000 digits, or even 10,000 digits.

That’s when you need to use a high-precision algorithm, which is essentially an array that stores each bit, and then you manually simulate the process as you add and subtract, and then you get the result.

It should be noted that: in order to facilitate calculation, it is usually stored backwards. For example, 12345 will be stored as {5, 4, 3, 2, 1}.

Addition template

Think back to our usual calculation of addition steps, is it the same as the following?

Write the addition of high precision algorithm is to simulate the last process, but because we store the way is backward, so do not need to start from right to left to add, add sequentially, record each carry, and finally calculate the results.

P1601 A + B Problem (high precision) – lo | computer science education new valley ecology (luogu.com.cn)

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

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

    if (t) C.push_back(1); // If you can carry at the end, carry

    return C;
}

int main(a)
{
    string a, b; cin >> a >> b;
    vector<int> A, B, C;
    for (int i = a.length() - 1; i >= 0; i--) / / save backwards
        A.push_back(a[i] - '0'); // Convert character to numeric type by subtracting '0'.
    for (int i = b.length() - 1; i >= 0; i--)
        B.push_back(b[i] - '0');

    C = add(A, B);

    for (int i = C.size() - 1; i >= 0; i--) // Output backwards
        cout << C[i];

    return 0;
}
Copy the code

Subtraction template

The thing about subtraction is, if we subtract a large number from a small number, we get a negative number, so we subtract a large number from b, and then we add the negative sign.

P2142 high-precision subtraction – lo | computer science education new valley ecological (luogu.com.cn)

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

bool cmp(vector<int> &A, vector<int> &B) // Which is bigger, A or B
{
    if (A.size() != B.size()) return A.size() > B.size(a);for (int i = A.size(a); i >=0; i--)
        if(A[i] ! = B[i])return A[i] > B[i];
    return true;
}


vector<int> sub(vector<int> &A, vector<int> &B)
{
    if (!cmp(A, B)) return sub(B, A); // If a decimal is subtracted from a large number, the result of a large number is returned
    int t = 0; vector<int> C;
    for (int i = 0; i < A.size() || i < B.size(a); i++) { t = A[i] - t;if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        t = (t < 0 ? 1 : 0);
    }

    while (C.size(a) >1 && C.back() = =0) C.pop_back(a);return C;
}

int main(a)
{
    string a, b; cin >> a >> b;
    vector<int> A, B, C;
    for (int i = a.length() - 1; i >= 0; i--)
        A.push_back(a[i] - '0');
    for (int i = b.length() - 1; i >= 0; i--)
        B.push_back(b[i] - '0');

    C = sub(A, B);
    if (!cmp(A, B)) cout << The '-'; // If you subtract a large number from a decimal, you should add a negative sign.

    for (int i = C.size() - 1; i >= 0; i--)
        cout << C[i];

    return 0;
}
Copy the code

Multiplication template

High precision byint

Similar to the above addition template.

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(a) >1 && C.back() = =0) C.pop_back(a);// remove the leading 0

    return C;
}
Copy the code

High accuracy multiplied by high accuracy

Open a C array to store the final result, add the result of each middle multiplication directly to the final result, and carry the final result.

P1303 valley A * B Problem – lo | computer science education new ecological (luogu.com.cn)

vector<int> mul(vector<int> &A, vector<int> &B)
{
    int len = A.size() + B.size(a);vector<int> C(len);

    for (int i = 0; i < A.size(a); i++)for (int j = 0; j < B.size(a); j++) C[i + j] += A[i] * B[j];// Add the result of each multiplication directly to the final result

    for (int i = 0; i < len; i++)
        if (C[i] > 9) // Carry if you can
        {
            C[i + 1] += C[i] / 10;
            C[i] %= 10;
        }

    while (C.size(a) >1 && C.back() = =0) C.pop_back(a);// remove the leading 0

    return C;
}
Copy the code

The usage of these two templates depends on the specific requirements of the topic.

Divide the template

The difference in division is that, instead of counting successive digits indefinitely, division returns the quotient and remainder.

High-precision division of int, the function returns the quotient, r is the outgoing remainder.

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C; r = 0;
    // If you recall division, we do it in order, because we store it backwards, so we also iterate backwards.
    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()); // Flip the array
    while (C.size(a) >1 && C.back() = =0) C.pop_back(a);// go to prefix 0

    return C;
}
Copy the code

The title

To increase the

P1009 factorial valley – the sum of los | computer science education new ecological (luogu.com.cn)