高精度加法

C从0到C.size( )为低位到高位

vector<int> add( vector<int> &A, vector<int> &B ) {
    if ( A.size() < B.size()) return add(B,A);
    int t = 0;
    vector<int> C;
    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;

}

高精度减法

比较函数

比较A,B位数大小函数
（高精度减法需保证A位数大于B，若A<B, 则先计算B-A再加上括号）

bool cmp( vector<int> &A, vector<int> &B ) {
    if ( A.size() != B.size()) return A.size() > B.size();
    // 未返回则说明A,B位数相同
    // 从高位开始比较,直到遇到一个不同的数再比较大小
    for ( int i = A.size()-1; i>=0; i-- ) {
        if ( A[i] != B[i] ) return A[i] > B[i]; 
    }
    return true;
}

vector<int> sub( vector<int> &A, vector<int> &B ) {
    vector<int> C;
    //  t表示借位，为0或1
    int t = 0;
    for ( int i=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;
    }
    // 去掉前导0
    while ( C.size() > 1 && C.back() == 0 ) C.pop_back();
    return C;
}

高精度乘法

一个大数×一个小数
对于A的每一位数都跟整个b相乘而不是一位一位计算

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;
}

高精度除法

一个大数除一个小数

// r 存储余数
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;
    }
    // C存储由高位到低位
    reverse(C.begin(), C.end());
    while ( C.size() > 1 && C.back() == 0 ) C.pop_back();
    return C;

}