高精度运算

高精度加法

给定两个正整数（不含前导 0），计算它们的和。
输入格式 共两行，每行包含一个整数。
输出格式 共一行，包含所求的和。
数据范围 1≤整数长度≤100000

#include<iostream>
#include<vector>

using namespace std;

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;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    //将a,b的每一位都存到A,B中，低位在前高位在后，便于处理
    //-'0' 操作使字母变成数字
    
    auto C = add(A,B);
    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);//按照人类习惯，高位在前低位在后输出
    return 0;
}

高精度减法

给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式 共两行，每行包含一个整数。
输出格式 共一行，包含所求的差。
数据范围 1≤整数长度≤105

#include<iostream>
#include<vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B){//判断是否有 A >= 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 1;
}

vector<int> sub(vector<int> &A, vector<int> &B){
   
    vector<int> C;
    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);//如果t>=0,push_back(t)
                                  //如果t<0,push_back(t + 10)，两种情况写在一起，(t + 10)%10
       if(t < 0) t = 1;
       else t = 0;
    }
    //去前导零
    while(C.size() > 1 && C.back() == 0) C.pop_back(); 
    return C;
}

int main(){
    string a,b;
    cin>>a>>b;
    vector<int> A,B;
    
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    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;
}

高精度乘法

给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。
输入格式 共两行，第一行包含整数 A，第二行包含整数 B。
输出格式 共一行，包含 A×B 的值。
数据范围 1≤A的长度≤100000,0≤B≤10000

#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很精髓，不用再判断最高位是否进位
           if(i < A.size()) t += A[i] * b;
           C.push_back(t % 10);
           t /= 10;
    }
    while(C.back() == 0 && C.size() > 1) 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');
    
    auto C = mul(A,b);
    
    for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    return 0;
}

高精度除法

给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。
输入格式	共两行，第一行包含整数 A，第二行包含整数 B。
输出格式	共两行，第一行输出所求的商，第二行输出所求余数。
数据范围	1≤A的长度≤100000,1≤B≤10000,B 一定不为 0

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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;
    }
    reverse(C.begin(), C.end());//此时C的第一位存储的是最高位，需要reverse一下
    while(C.size() > 1 && C.back() == 0) C.pop_back();//去前导零
    return C;
}

int main(){
    int b;
    vector<int> A;
    string a;
    cin>>a>>b;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    int 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;
}