数据

  • 数据输入

vector<int> read(){
	string s;
    cin >> s;
    vector<int> C;
    for(int i = s.size() - 1;i >= 0;i--){
		int x = s[i] - '0';
        C.push_back(x);
    }
    return C;
}

  • 数据输出

void write(vector<int> C){
    for(int i = C.size() - 1;i >= 0;i--){
        cout << C[i];
    }
}

1 高精度加法

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

  • 题目追踪：

    • A + B Problem II

    • 数楼梯

2 高精度减法

bool cmp(vector<int> A,vector<int> B){
    if(A.size() != B.size()) return A.size() > B.size();
    else {
        for(int i = A.size() - 1;i >= 0;i--){
            if(A[i] != B[i]) return A[i] > B[i];
        }
    }
    return true;
}


vector<int> mul(vector<int> A,vector<int> B){
    int carry = 0;
    vector<int> C;
    for(int i = 0;i < A.size();i++){
		carry = A[i] - carry;
        if(B.size() > i) carry -= B[i];
        C.push_back((carry + 10) % 10);
        carry = carry < 0 ? 1 : 0;
    }
	while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

3 高精度 * 低精度

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

  • 题目追踪：

    • 阶乘之和

4 高精度 * 高精度

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

  • 题目追踪：

    • A + B Problem II

    • 数楼梯

5 高精度 / 低精度

6 高精度 / 高精度