[AcWing 791]高精度加法

#include <iostream>
#include <vector> //含有size方法
using namespace std;

//C = A+B
vector<int> add(vector<int> &A, vector<int> &B){
    vector<int> C;
    int t = 0; //t表示进位
    
    for(int i = 0; i < A.size() || i < B.size(); i++){
        if(i < A.size()) t += A[i]; //加上加数A上的某位
        if(i < B.size()) t += B[i]; //加上加数B上的某位
        //此时的t表示: 上次运算产生的进位 + A[i] + B[i]
        C.push_back(t % 10); //本次运算的结果 模10后 放入数组C中
        t /= 10; //表示本次运算产生的进位 比10大则t=1 比10小则t=0 (逢十进一)
    }
    
    if(t) C.push_back(1); //最高位产生进位时 结果C中新增一个最高位 为1
    
    return C;
}

int main(){
    string a, b; //使用字符串的形式输入
    cin >> a >> b; //a = "123456"
    
    vector<int> A, B; //将输入的字符串转化为数字存到数组中 先存放个位 最后存放最高位
    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;
}




/*
四种情况：
A+B 
两个大整数相加    
A和B的位数大概是10的6次方

A-B   
两个大整数相减   
A和B的位数大概是10的6次方

A*a   
 一个大整数乘上一个小整数    
A的位数 <= 10的6次方  
a的数值 <= 10的9次方

A/b
求商和余数是多少


两个问题：
一、
大整数的存储 ---> 用数组
每一位存到一个数组里面
存时 
数组下标0 存个位
数组下标1 存十位
数组下标2 存百位
........以此类推
低位存到数组中第一个位置
因为两个整数相加可能会进位
在数组末尾添加数字较容易

二、
运算  模拟人工加法的过程
     A3  A2   A1  A0
+        B2   B1  B0
--------------------------
     C3  C2   C1  C0
对于每一位:  Ai + Bi + t
t 表示上一位的进位: 
无进位时t=0 有进位时t=1

*/