AcWing 高精度模板

算法思路：

1. 当输入的数很大时，可采用字符串方式接收。

2. 拆成一位一位的数字，把它们存在一个数组中，一个数组元素表示一位数字

数组中是这样存储的：

倒序存储原因：

在平常，数字从左到右依次为从高位到低位....可这里却与日常的习惯相反。

这是因为加法可能会产生进位，而数组在最前面加上数字是不可能的，但在尾巴处加上数字是好做的，所以，倒着放。

791. 高精度加法

1、高精度加法模板

#include 

using namespace std;

/**
 * 功能：高精度加法
 * @param A 大整数a
 * @param B 大整数b
 * @return 结果
 */
vector add(vector &A, vector &B) {
    //保证位数大的在前
    if (A.size() < B.size()) return add(B, A);
    //结果数组
    vector C;
    //进位
    int t = 0;
    //从低位到高位（注意数组里的数字是反着放的~）
    for (int i = 0; i < A.size(); i++) {
        t += A[i];//加上进位
        if (i < B.size()) t += B[i];//如果B此位置存在数字,则加上B此位置上的数字。
        C.push_back(t % 10);//模10保留本位，产生进位（如果有的话）
        t /= 10;//算出进位的值
    }
    //如果最后还有一个进位存在，需要在最后面加上它（这个最后面，其实是真正数字的最前面）
    if (t) C.push_back(t);
    return C;
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    //大数当做字符串读入
    string a, b;
    cin >> a >> b;
    //声明三个vector用来装拆开的字符串中每一个数字。注意这里的vector声明为局部变量，不宜声明为全局变量。
    vector A, B, C;
    //需要倒着装入vector
    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');

    //调用模板进行加法运算
    C = add(A, B);
    //倒序输出
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    return 0;
}

792. 高精度减法

2、高精度减法模板

#include 

using namespace std;
/**
 * 功能：计算两个向量整数数组的减法
 * @param A 第一个数组
 * @param B 第二个数组
 * @return 结果
 */
vector sub(vector &A, vector &B) {
    int t = 0; //借1当10
    vector C;//结果数组
    //从低位开始
    for (int i = 0; i < A.size(); i++) {
        t = A[i] - t;//如果有借位，那么先减去这个1
        if (i < B.size()) t -= B[i];//如果B数组此位置有数，需要减去
        C.push_back((t + 10) % 10); //本位该保留的值,如果不够减，就借一位1，当10
        if (t < 0)t = 1; else t = 0;//如果不够减，就告诉上一位，借了一个1
    }
    //去掉前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
/**
 * 功能：对比两个数组的大小
 * @param A 第一个数组
 * @param B 第二个数组
 * @return 是不是A>B
 */
bool cmp(vector &A, vector &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;
}


int main() {
    //优化输入
    ios::sync_with_stdio(false);
    //输入的两个大数a和b
    string a, b;
    cin >> a >> b;
    //声明
    vector A, B, C;
    //倒序放入
    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)) C = sub(A, B);
    else {
        printf("-");
        C = sub(B, A);
    }
    //反着输出
    for (int i = C.size() - 1; i >= 0; i--)printf("%d", C[i]);
    return 0;
}

793. 高精度乘法

3、高精度乘以低精度模板

#include 

using namespace std;
/**
 * 功能：高精度乘法(高精乘低精)
 * @param A 第一个数字
 * @param b 第二个数字(低精)
 * @return 结果
 */
vector mul(vector &A, int b) {
    int t = 0;//进位
    vector C;//结果
    //从低位开始
    for (int i = 0; i < A.size(); i++) {
        t += A[i] * b;//当前位结果，如果有进位，加上进位
        C.push_back(t % 10);//保留当前位
        t /= 10;//产生进位（如果有的话）
    }
    //如果最后还有进位，那么添加上
    if (t) C.push_back(t);
    //去除前导0,比如b是0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    string a;
    int b;
    cin >> a >> b;
    vector A, C;
    //倒序输入
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    //调用模板相乘
    C = mul(A, b);
    //反着输出结果
    for (int i = C.size() - 1; i >= 0; i--)printf("%d", C[i]);
    return 0;
}

4、高精度乘以高精度模板

#include 

using namespace std;

/**
 * 功能：高精度乘高精度模板
 * @param A
 * @param b
 * @return
 */
vector mul(vector &A, vector &B) {
    //初始化大小
    vector C(A.size() + B.size());
    //先放里再说
    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    //处理余数
    for (int i = 0, t = 0; i < C.size(); i++) {
        t += C[i];
        if (i >= C.size()) C.push_back(t % 10);
        else C[i] = t % 10;
        t /= 10;
    }
    //去掉前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main() {
    string a, b;
    cin >> a >> b;
    //准备动作
    vector 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');
    //计算
    vector C = mul(A, B);
    //倒序输出
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    return 0;
}

794. 高精度除法

5、高精度除以低精度模板

#include 

using namespace std;

/**
 * 功能：高精除低精模板
 * @param A 第一个数
 * @param b 第二个数（低精）
 * @param r 余数（返回）
 * @return 结果
 * 传引用不会复制A，快
 */
vector div(vector &A, int b, int &r) {
    vector C;
    r = 0;
    //这里是从高位开始的，注意！在除法运算中，高位到低位运算
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];//将余数放大10倍，再加上当前位
        C.push_back(r / b);//保留本位
        r %= b;//继续余数
    }
    //例子：
    //7319951122 除 19 = 0385260585 余 7
    //因为需要去掉前导0，而C++没有快速办法将数组头部元素干掉，
    //只有O(1)的办法将尾部的元素干掉，所以先把结果倒过来。
    reverse(C.begin(), C.end());
    //利用pop_back()去除前导0,就成了585062583,然后在main函数中再倒序输出即可
    //585062583->385260585
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    string a;
    int b;
    vector A, C;
    cin >> a >> b;
    //一道题目可能会涉及多种运算，顺序统一更容易处理
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    int r;//余数
    //调用模板
    C = div(A, b, r);
    //倒序输出
    for (int i = C.size() - 1; i >= 0; i--)printf("%d", C[i]);
    printf("\n%d ", r);
    return 0;
}