1.基础算法 - 高精度，前缀和与差分

高精度算法一般考四种：在java和python中不需要考虑这个问题。因为java中有大整数类。
1.两个大整数相加A + B ,一般位数在10的6次方！
2.两个大整数相减A - B
3.一个大整数乘一个小整数 A * a len（A）<=1e6, a <=1e9
4.A / a 求商和余数
大整数，在c++中都是通过数组的方式一位一位的存起来的， 在存的时候的技巧是：数组的起始位置存个位。这是因为，数组的最后以为是整个大整数的最高位，因为在计算过程中，会产生进位问题，这样可以把进位标志append到数组的后面。更方便。
学编程不能止于思路，一定一定要落实到代码上。

#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;
//C = A + B
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;
}

int main(){
    string a, b;
    vector<int> A,B;
    cin >>a>>b; //a = "123456"
    for(int i = a.size() - 1; i >=0;i --) A.push_back(a[i] - '0'); //A = [6,5,4,3,2,1]
    for(int i = b.size() - 1; i >=0;i --) B.push_back(b[i] - '0');

    auto C = add(A,B);
    for(int i = C.size() - 1; i>=0; i--) printf("%d", C[i]);
    return 0;

}

高精度减法的代码：

#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;

//判断是否A>= B
bool cmp(vector<int> &A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size()>B.size();
    for(int i = A.size() - 1; i >=0; i--)
    {
        if(A[i] != B[i]) return A[i]>B[i];
    }
    return true;
}
//C = A + B
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();  //去掉前导0
    return C;
}

int main(){
    string a, b;
    vector<int> A,B;
    cin >>a>>b; //a = "123456"
    for(int i = a.size() - 1; i >=0;i --) A.push_back(a[i] - '0'); //A = [6,5,4,3,2,1]
    for(int i = b.size() - 1; i >=0;i --) B.push_back(b[i] - '0');
    if(cmp(A,B))
    {
        auto C = sub(A,B);
        for(int i = C.size() - 1; i>=0; i--) printf("%d", C[i]);
    }
    else
    {
        auto C = sub(B,A);
        printf("-");
        for(int i = C.size() - 1; i>=0; i--) printf("%d", C[i]);
    }

    return 0;

}

高精度乘法，这个代码和高精度加法很像，这里注意A*b的时候，要把b当成一个成体来算，而不是正常的一位一位的算，其实自己用笔算的时候，如果一个b不是很大，也可以采用这种方式提高效率。

#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size() || t; i++)    //这里的t主要是判断当循环结束之后，t的进位是否还有值
    {
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}
int main()
{
    string a;
    int b;
    cin >> a >>b;
    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    auto C = mul(A,b);
    for(int i = C.size() - 1; i >=0; i--) printf("%d", C[i]);
    return 0;

}

高精度除法：因为除法是从最高位开始的，因此正常情况下，可以在处理读入字符串，存入数组的时候，字符串首位存最高位。但是考虑到一个系统的加减乘除可以通用的情况，所以还是反序的存储。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> div(vector<int> &A, int b, int &r)   //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;

    }
    //因为当前的C[0]是最高位，和大整数乘法是逆过来的，所以要用algorithm中的reverse函数处理一下
    reverse(C.begin(), C.end());
    while(C.size() >1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    int b;
    cin >> a >>b;

    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    int r ; //余数,输出时r是通过引用的方式取回的
    auto C = div(A,b,r);
    for(int i = C.size() - 1; i >=0; i--) printf("%d", C[i]);
    cout << endl << r <<endl;
    return 0;

}

前缀和

差分