题解 | #Powerful Calculator#

题意：输入两个巨长无比的整数a,b;输出a+b,a-b,a*b

思路：因为整数非常大，所以考虑用字符串模拟的方法处理。 输入两行字符串，处理字符串：将每位数字反向压入vector中（因为+,-,*都是从低位向高位处理，所以反向压入）。

分别对两个vector A，B执行加法，减法（考虑两者大小关系），乘法，最后对结果反向输出即可。

处理字符串：

for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//倒序压入数组中
for(int j=b.size()-1;j>=0;j--) B.push_back(b[j]-'0');//因为所有的计算都是从低位到高位，倒序方便计算

vector加法： 思路：对A[i],B[i]逐位相加，处理进位并取结果的个位数 若最高位加完后仍有进位，则push_back(1)

vector<int> add(vector<int> &A,vector<int> &B)//画图，思考加法的过程
{
    vector<int> res;
    int sum=0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size()) sum+=A[i];//逐位相加
        if(i<B.size()) sum+=B[i];
        res.push_back(sum%10);//取加和的个位数
        sum/=10;//表示进位位
    }

    if(sum) res.push_back(1);//若最高位加完后sum表示的进位位不是0，则再进位1
    return res;
}

vector比较，比较两个vector代表的整数的大小（为vector的减法做铺垫）

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 true;//A==B
}

vector减法： 对t的处理非常巧妙： 若A[i]>B[i]，则直接t为正，即为该位所求 若A[i]<B[i],则需要向高位借位，此时t为负，但该位结果为(A[i]-t-B[i]+10)%10，t置1表示该位存在向高位借位，方便高位下次计算时-1

若减法完成后高位存在0，则将0删去，保证vector内保存的数字的合法性

vector<int> sub(vector<int> &A,vector<int> &B)//A>B , 返回A-B
{
    vector<int> res;
    int t=0;
    for(int i=0;i<A.size();i++)
    {   //这两行合起来看，画一个减法的式子帮助理解
        //t起到了借位的作用，若A[i]>=B[i]，则t存储减完后的数字
        //若A[i]<B[i]，t<0.则(t+10)%10模拟借位后的减法过程
        t=A[i]-t;
        if(i<B.size()) t=t-B[i];

        res.push_back((t+10)%10);
        if(t<0) t=1;//有借位，则下一个高位-1
        else t=0;//无借位
    }

    while(res.size()>1&&res.back()==0) res.pop_back();//若减法完成后高位存在0，则将0删去
    return res;
}

vector乘法： 模拟乘法式的过程即可：

vector<int> mul(vector<int> &A,vector<int> &B)
{
    int m=A.size(),n=B.size();
    vector<int> res(m+n);//m*n的乘法，结果最大为m+n位
    //列出乘法的式子，帮助思考
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            res[i+j]+=A[i]*B[j];

    for(int i=0;i<m+n;i++)
        if(res[i]>10){//若该位乘积>10，进位
            res[i+1]+=res[i]/10;//向上进位
            res[i]=res[i]%10;//本位取余
            }
    while(res.size()>1&&res.back()==0) res.pop_back();//若乘法完成后高位存在0，则将0删去（原因：乘积位数可能未达到m+n，但vector初始化了m+n个0）
    return res;
}

C++代码：

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;

void print(vector<int> &A)//自定义输出函数，倒序输出vector中的元素
{
    for(int i=A.size()-1;i>=0;i--)
        printf("%d",A[i]);

    printf("\n");
}

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 true;//A==B
}

vector<int> add(vector<int> &A,vector<int> &B)//画图，思考加法的过程
{
    vector<int> res;
    int sum=0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size()) sum+=A[i];//逐位相加
        if(i<B.size()) sum+=B[i];
        res.push_back(sum%10);//取加和的个位数
        sum/=10;//表示进位位
    }

    if(sum) res.push_back(1);//若最高位加完后sum表示的进位位不是0，则再进位1
    return res;
}

vector<int> sub(vector<int> &A,vector<int> &B)//A>B , 返回A-B
{
    vector<int> res;
    int t=0;
    for(int i=0;i<A.size();i++)
    {   //这两行合起来看，画一个减法的式子帮助理解
        //t起到了借位的作用，若A[i]>=B[i]，则t存储减完后的数字
        //若A[i]<B[i]，t<0.则(t+10)%10模拟借位后的减法过程
        t=A[i]-t;
        if(i<B.size()) t=t-B[i];

        res.push_back((t+10)%10);
        if(t<0) t=1;//有借位，则下一个高位-1
        else t=0;//无借位
    }

    while(res.size()>1&&res.back()==0) res.pop_back();//若减法完成后高位存在0，则将0删去
    return res;
}

vector<int> mul(vector<int> &A,vector<int> &B)
{
    int m=A.size(),n=B.size();
    vector<int> res(m+n);//m*n的乘法，结果最大为m+n位
    //列出乘法的式子，帮助思考
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            res[i+j]+=A[i]*B[j];

    for(int i=0;i<m+n;i++)
        if(res[i]>10){//若该位乘积>10，进位
            res[i+1]+=res[i]/10;//向上进位
            res[i]=res[i]%10;//本位取余
            }
    while(res.size()>1&&res.back()==0) res.pop_back();//若乘法完成后高位存在0，则将0删去（原因：乘积位数可能未达到m+n，但vector初始化了m+n个0）
    return res;
}

int main()
{
    string a;
    string b;
    vector<int> A;//存储字符串A转化的数字
    vector<int> B;//存储字符串B转化的数字
    while(cin>>a>>b)
    {
        for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//倒序压入数组中
        for(int j=b.size()-1;j>=0;j--) B.push_back(b[j]-'0');//因为所有的计算都是从低位到高位，倒序方便计算

        vector<int> add_ans=add(A,B);//计算a+b的和
        print(add_ans);//自定义print函数

        vector<int> sub_ans;
        if(cmp(A,B)) sub_ans=sub(A,B);//A>B直接减
        else//A<B，则输出 -sun(B,A)
        {
            sub_ans=sub(B,A);
            printf("-");
        }
        print(sub_ans);

        //计算A*B
        vector<int> mul_ans;
        mul_ans=mul(A,B);
        print(mul_ans);

    }

    return 0;
}