高精度计算的思想与实现

OI界有一句老话:
三年OI一场空，不开long long见祖宗

这句话，我真的是牢牢记在心里，所以每一次WA的时候，第一个想到的就是改用longlong

但是，即使开了unsigned long long，不够用的情况还是非常常见

于是，我们就必须写高精度算法处理数据

对！高精度看名字本来是精度高，但我们一般用它解决长度不够用的问题

高精度的思想其实非常简单，本质就是用数组来模拟一个整数，用自定义的函数完成加减

它的核心就是：用数组模拟！

那么，怎么用数组模拟呢？

第一个很重要的点就是：存放倒序的数字！

为什么要倒序存放数字呢？

因为这样我们就不用花时间对齐数字了！

这样，个位就永远是第一个元素，十位就是第二个

而且，在做乘法时，每两位相乘的最低位的位置也可以得到

第二点，就是进位，退位

用一个数字x表示进位的量就可以啦！

退位就直接下一位减一，本位加10就可以了，因为后面就会处理到的！

上模板！
常用模板：
1,减法
2，高精度比较
3，输出
4，除法（高精除高精）
5.乘法（高精乘低精）

deque<int> minuse(deque<int> a,deque<int> b){
    deque<int> c;
    for(int i=0;i<a.size();i++) c.push_back(0);
    for(int i=0;i<a.size();i++){
        if(i<b.size()){
            if(a[i]<b[i]){
                a[i]+=10;
                a[i+1]--;
            }
            c[i]=a[i]-b[i];
        }else{
            c[i]=(a[i]>=0)? a[i] : (a[i]+10,a[i+1]--);
        }
    }
    return c;
}





bool compare(deque<int> a,deque<int> b){
    while(a.back()==0 && a.size()>1) a.pop_back();
    while(b.back()==0 && b.size()>1) b.pop_back();
    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;
}





void print(deque<int> a){
    while(a.back()==0 && a.size()>1) a.pop_back();
    for(int i=a.size()-1;i>=0;i--) cout << a[i];
    cout<<" ";
}





deque<int> chu(deque<int> a,deque<int> b){
    deque<int> c;
    for(int i=0;i<a.size();i++){
        c.push_back(0);
    }
    for(int i=0;i<a.size()-1;i++){
        b.push_front(0);
    }
    for(int i=a.size()-1;i>=0;i--){
        for(int j=0;j<9;j++){
            if(compare(a,b)){
                //print(a);print(b);print(c);
                //cout << endl;
                a=minuse(a,b);
                //print(a);print(b);print(c);
                //cout << endl;
                c[i]++;
            }else{
                break;
            }
        }
        b.pop_front();
    }
    print(c);
    cout << endl;
    print(a);
    return c;
}


deque<int> multi(deque<int> a,int b){
    deque<int> c;
    for(int i=0;i<a.size()+int(log10(b)+1);i++){
        c.push_back(0);
    }
    int x=0;
    for(int i=0;i<a.size();i++){
        c[i]=x+a[i]*b;
        x=c[i]/10;
        c[i]%=10;
    }
    for(int i=0;x!=0;i++){
        c[a.size()+i]=x%10;
        x/=10;
    }
    while(c.back()==0 & c.size()>1) c.pop_back();
    return c;
}