高精度

问题引入

在C++的语法部分已经介绍了几种数据类型，并且已经知道了每种数据类型能够容纳的数字范围是有限的。一般情况下用int类型，如果数字更大一点还可以使用long long类型，如果需要存储或者使用更大的整数计算该怎么办呢？

可以选择使用数组的方式存储很大整数的每一位，可以让计算机模拟我们计算加减乘除的方式来计算大数的加减乘除，下面我们就来逐一分析高精度的加减乘除。

高精度加法

【例题1】
A+B Problem（高精度加法）。输入两个不超过500位的正整数，计算它们的和。
【思路分析】
我们可以用数组来模拟非常长的整数，这意味着可以用数组的每一位记录这个整数的每一位。也就是可以用n位数组来记录一个n位数字。
解决了存储问题，再来回顾一下竖式加法。结合下图，分析高精度加法的思路。

竖式加法的实质就是模拟每一位的加法与进位。对于十进制加法来说，某一位上的和超过9时会产生进位现象，进位就是保留那一处数字的个位数，然后把十位上的数字加给下一位去。同时我们应该注意到，必须是从低位到高位逐位相加和处理进位的，否则会发生顺序上的错误。

最终整理得到以下思路：
① 用两个字符串读入高精度整数；
② 由于要从右向左计算、从右向左进位，因此将每一位逆序存入两个整型数组中；
③ 从左向右逐位做计算，逐位进位；
④ 逆序输出计算结果。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int a[520], b[520], c[520]; //ab数组用来存两个大数，c数组存大数的和
string s1, s2;
int main() {
    cin >> s1 >> s2;
    int len = max(s1.size(), s2.size());
    for (int i = 0; i < s1.size(); i++) { //倒序存储
        a[s1.size() - i - 1] = s1[i] - '0';
    }
    for (int i = 0; i < s2.size(); i++) {
        b[s2.size() - i - 1] = s2[i] - '0';
    }
    for (int i = 0; i < len; i++) {
        c[i] += a[i] + b[i]; //当前位求和
        c[i + 1] = c[i] / 10; //十位进位
        c[i] %= 10;//保留个位
    }
    if (c[len]) len++; //最高位是1，则总长+1
    for (int i = len - 1; i >= 0; i--) { //逆序输出
        cout << c[i];
    }
}

这里还可以使用字符串的解法来求解。参考代码如下：

#include <bits/stdc++.h>
using namespace std;
string s1, s2, ans;
int len, t; //t表示当前这一位的和
int main() {
    cin >> s1 >> s2;
    len = max(s1.size(), s2.size());
    reverse(s1.begin(), s1.end()); //翻转s1和s2
    reverse(s2.begin(), s2.end());
    for (int i = 0; i < len; i++) { //逐项相加，逐项进位
        if (i < s1.size()) t += s1[i] - '0';
        if (i < s2.size()) t += s2[i] - '0';
        ans += char(t % 10 + '0'); //使用字符串的拼接操作
        t /= 10;
    }
    if (t) ans += char(t + '0'); //处理最终是否进位
    reverse(ans.begin(), ans.end()); //计算完还要翻转
    cout << ans;
    return 0;
}

高精度减法

【例题2】
A-B Problem（高精度减法）。输入两个不超过500位的的正整数，计算它们的差。
【问题分析】
和高精度加法一样，我们结合下边的竖式减法来理解高精度减法的思路。

竖式减法的实质是模拟每一位的减法与借位。对于十进制减法来说，还是要先从最低位开始减，某一位上的数字不够减时，就从更高位借10来进行减法操作。例如右边的十位数字6想去减十位数字的9时会不够减，我们就从968的百位的9借1当成10，这样16就够减9的了。还应注意到如果A<B，会出现负的情况，此时继续用大数减去小数来计算，最后的结果前面添加一个负号即可。

最终整理得到以下思路：
① 用两个字符串读入高精度整数；
② 判断结果的正负。若结果为负，则先交换两个字符串，保证用大数减小数；
③ 将每一位逆序存入两个整型数组中；
④ 从左向右，逐位相减。若不够减，则借位；
⑤ 逆序输出计算结果（若结果为负，别忘了负号）

之前我们学习了函数的写法，我们可以把高精度的减法封装为函数。示例代码的sub函数要确保a>=b，并且a和b中没有负号。
代码如下：

#include <bits/stdc++.h>
using namespace std;
string sub(string a, string b) { //保证a>=b，且都没有负号
    string ret;
    reverse(a.begin(), a.end()); //逆序
    reverse(b.begin(), b.end());
    for (int i = 0, t = 0; i < a.size(); i++) { //逐位相减
        t = a[i] - '0' - t;  
        if (i < b.size()) t -= b[i] - '0'; //t用来记录当前项的值
        ret += char( (t + 10) % 10 + '0'); //涵盖t为正负的两种情况
        if (t < 0) t = 1; //在这里t记录是否借位
        else t = 0;
    }
    reverse(ret.begin(), ret.end()); //翻转ret
    while (ret.size() > 1 && ret[0] == '0') { //删除最高位的若干个0
        ret.erase(0, 1); // 从0下标开始删，删1个
    }
    return ret;
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    bool f = false; //默认不需要负号
    if ((s1.size() < s2.size()) || (s1.size() == s2.size() && s1 < s2)) {
        swap(s1, s2);
        f = true; // 标记需要添加负号
    }
    if (f) cout << "-";
    cout << sub(s1, s2);
}

注意：
（1）两个数相减可能会得到若干个0，比如1234-1230会得到0004，所以要去掉前面的若干个0。去掉0的时候，至少要保留1个0，即需要确保字符串ret不为空，因此要求ret.size()>1。
（2）第10行的(t+10)%10涵盖了t正负两种情况：①t>=0时输出t%10；②t<0时输出t+10。

高精度乘法

【例题3】
A* B Problem（高精度乘法）。输入两个不超过500位的的正整数，计算它们的乘积。
【问题分析】
还是以竖式乘法为例，我们一起分析高精度乘法的思路。

和加法一样的是，当某两位相乘的结果大于9则会产生进位；不同的是，乘法的运算会把两个数的每一位都匹配一遍，得到相乘的结果。

举个例子：514×495。注意到当我们拿第一个数514乘以第二个数的十位9时，我们会产生一个错位。
方便起见，我们认定个位放在0下标，十位放在1下标，以此类推。（能不能从1下标开始计算呢？感兴趣的同学可以自己分析并实现相应的代码）

为了更加清晰地理解中间进位和运算的过程，结合下面图片来分析：

观察每列不难发现，a[i]* b[j]的贡献全都在中间产物的第i+j位上。由于这里需要计算乘法，而且最终放到结果数组里还需要再次mod 10，所以我们选择开辟三个int类型的数组计算更方便。

总结一下思路：
① 需要三个数组a、b、c，其中a和b用来逆序存放两个正整数，c数组用来存放相乘之后的结果；
② 双重循环求a×b。当a数组的第i位要乘以b数组的第j位得到的结果应该放在c数组的i+j位。当a[i]* b[j]加上原本c[i+j]上的数字超过了9，就需要进位了；
③ 在某些特殊情况下，c数组的较高位会有若干个0，需要去掉。去掉的时候和减法一样，还应至少保留一个0；
④ 最终逆序输出c数组即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
string mul(string s1, string s2) {
    string ret;
    int a[520] = {0}, b[520] = {0}, c[1020] = {0};
    int la = s1.size(), lb = s2.size();
    for (int i = 0; i < s1.size(); i++) { //1.逆序存放到a、b数组中
        a[s1.size() - i - 1] = s1[i] - '0';
    }
    for (int i = 0; i < s2.size(); i++) {
        b[s2.size() - i - 1] = s2[i] - '0';
    }
    for (int i = 0; i < lb; i++) { //2.双重循环求乘积，放到c数组里
        for (int j = 0; j < la; j++) {
            c[i + j] += a[j] * b[i]; //求乘积
            c[i + j + 1] += c[i + j] / 10; //进位
            c[i + j] %= 10; //保留个位
        }
    }
    int idx = la + lb; //3.去掉高位的若干个0，至少保留一个0
    while (idx && !c[idx])   idx --;
    
    for (int i = idx; i >= 0; i--) //4.逆序存放到字符串ret中
        ret += char(c[i] + '0');
    return ret;
}
int main() {
    string a, b;
    cin >> a >> b;
    cout << mul(a, b);
}

高精度除法（高精/低精）

【例题4】
A/B Problem（高精度除以低精度）。输入一个不超过500位的的正整数A和另一个不超过long long范围的正整数B，计算A/B的商（做整除）。
【问题分析】
同样的，结合竖式除法我们一起来分析思路。
竖式除法的求解过程：除法用竖式计算时，从被除数最高位开始除起，如若除不了，那么就用最高位和下一位合成一个数来除，直到能除以除数为止。

参考右图，A是8249，B是56。现在需要求解8249/59的商。考虑更一般的情况，直接从最高位开始除，除不了就商0。
即：
① 先拿8/56得到商为0，余数8；
② 8×10+2得到82，之后82/56得到商为01、余数26；
③ 继续拿余数26×10+4得到264，264/56得到商为014、余数40；
④ 接下来拿余数40×10+9得到409，409/56得到商为0147、余数为7。
⑤ 当A后面没有数字，就结束竖式除法。
最终得到商为147。

总结一下最终的思路，比较简单：
① 这里不需要逆序存储了，循环遍历A的每一位，求出当前的商和余数；
② 去掉前面若干个0；
③ 输出。

代码如下：

#include <bits/stdc++.h>
using namespace std;
string div(string a, long long b) {
    string ret;
    long long r = 0; //r存放余数
    for (int i = 0; i < a.size(); i++) {
        r = r * 10 + a[i] - '0'; //计算当前的被除数
        ret += char(r / b + '0'); // 求商并添加到字符串ret末尾
        r %= b; //求余数
    }
    while (ret.size() > 1 && ret[0] == '0') { //删除最高位的若干个0
        ret.erase(0, 1);
    }
    return ret;
}
int main() {
    string a;
    int m;
    cin >> a >> m;
    cout << div(a, m);
}

注：这里的ret.size() > 1和高精度减法一致，都是在删除若干个0时，确保还剩一位数字0。

拓展：高精度/高精度

//高精除以高精
//用计算机做高精度除法时，模拟日常除法的步骤。
//但计算机不可能做“试商”，这时，我们可以采
//用减法来模拟
//
//"试商"的过程。算法的步骤如下：
//
//1、将除数移动和被除数对齐，位数不够时，补0，
//
//2、利用被除数减去除数，一直减到被除数小于除
//数，减的次数，就是“试商”的结果，每移动一次。
//
//3、重复上述步骤，一直到被除数和除数的位数相等为止。
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
string s;
int a[256],b[256],c[256],len;
void print(int x[])//输出 
{
    if(x[0]==0)//去除无效高位 
    {
        cout<<0<<endl;
        return ;
    }
    for(int i=x[0];i>0;i--)
        cout<<x[i];
    cout<<endl;
    return ;
}
void reverse(int arr[])//反序 
{
    cin>>s;
    arr[0]=s.size();
    for(int i=1;i<=arr[0];i++)
        arr[i]=s[arr[0]-i]-'0';
}
void strcpy(int p[],int q[],int t)//每次取除数放到q当中，高位与被除数对齐 
{
    for(int i=1;i<=p[0];i++)//从高位到底为 
        q[i+(t-1)]=p[i]; //高位对其 
    q[0]=p[0]+(t-1);//长度一致 
}
int compare(int x[],int y[])//比较大小，看是否够减 
{
    if(x[0]>y[0])return 1;//x表示的数大于y表示的数 c[i]可以加多次 
    else if(x[0]<y[0])return -1;//x表示的数小于y表示的数 c[i]不可以加，判断a的下一位 
    else 
    {
        for(int i=x[0];i>0;i--)
        {
            if(x[i]>y[i])return 1;
            else if(x[i]<y[i])return -1;
        }
        return 0;//两数相等，c[i]只能加一次 
     } 
}
void sub(int x[],int y[])//减法运算 
{
    int i,flag;
    flag=compare(x,y);
    if(flag==0){
        x[0]=0;return ;//无余数 ，x最终存放的余数为0 
    }
    if(flag==1)//可以减 
    {
        for(i=1;i<=x[0];i++)
        {
            if(x[i]<y[i])
            {
                x[i+1]--;x[i]+=10;
            }
            x[i]-=y[i];
        }
        while(x[0]>0 && x[x[0]]==0)x[0]--;//x从高位到低位还未遍历完，并且高位有0 
        return ;
    }
    
} 
void numply(int a[],int b[],int c[])//确定商c 
{
    int temp[256];
    c[0]=a[0]-b[0]+1;//记录商的大致位数，并确定商的高位位置 
    for(int i=c[0];i>0;i--)//每次循环一次，除数要往后移一位，相当于高位减一 
    {
        memset(temp,0,sizeof(temp));
        strcpy(b,temp,i);//除数放到temp中，从i的位置开始赋值，为了高位对其 
        while(compare(a,temp)>=0)//对其后 可以减 
        {
            c[i]++;//第i为的值加1 
            sub(a,temp);//模拟减法，相当于在a[0]-a[i-1]构成的数里减去一个b[0]-b[1]构成的数 
        }
    }
    while(c[0]>0 && c[c[0]]==0)c[0]--;//去除高位为0的情况 
    return ;
}
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    reverse(a);
    reverse(b);
    numply(a,b,c);
    print(c);
    print(a);
    return 0;
 }