【模板】高精度加法、减法、乘法、除法

高精度加法：

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

高精度减法：

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

高精度乘法：

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

高精度除法：

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

高精度加法：

791. 高精度加法 - AcWing题库

代码：

#include<bits/stdc++.h>
#define rep(i,a,b)  for(int i=a;i<=b;i++)
#define rpe(j,b,a)  for(int j=b;j>=a;j--)
using namespace std;
vector<int> add(vector<int>&a,vector<int>&b){
    if(a.size()<b.size()) return add(b,a);
    vector<int> c;
    int t=0;
    rep(i,0,a.size()-1){
        t+=a[i];
        if(i<b.size()) t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t) c.push_back(t);
    return c;
}
int main(){
    string s1,s2;
    vector<int>a,b;
    cin>>s1>>s2;
    rpe(i,s1.length()-1,0) a.push_back(s1[i]-'0');
    rpe(i,s2.length()-1,0) b.push_back(s2[i]-'0');
    auto c=add(a,b);
    rpe(i,c.size()-1,0) cout<<c[i];
    return 0;
}

 压9位的代码：

#include <iostream>
#include <vector>

using namespace std;

const int base = 1000000000;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % base);
        t /= base;
    }

    if (t) C.push_back(t);
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;

    for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (a[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            A.push_back(s);
            s = j = 0;
            t = 1;
        }
    }
    for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
    {
        s += (b[i] - '0') * t;
        j ++, t *= 10;
        if (j == 9 || i == 0)
        {
            B.push_back(s);
            s = j = 0;
            t = 1;
        }
    }

    auto C = add(A, B);

    cout << C.back();
    for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
    cout << endl;

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/39792/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 792. 高精度减法 - AcWing题库

代码：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rpe(j,b,a) for(int j=b;j>=a;j--)
using namespace std;
bool cmp(vector<int>&a,vector<int>&b){
    if(a.size()!=b.size()) return a.size()>b.size();
    rpe(i,a.size()-1,0)
        if(a[i]!=b[i]) return a[i]>b[i];
    return true;
}
vector<int> sub(vector<int>&a,vector<int>&b){
    vector<int> c;
    int t=0;
    rep(i,0,a.size()){
        t+=a[i];
        if(i<b.size())  t-=b[i];
        c.push_back((t+10)%10);
        if(t<0) t=-1;
        else t=0;
    }
    while(c.back()==0&&c.size()>1) c.pop_back();
    return c;
}
int main(){
    string s1,s2;
    vector<int> a,b,c;
    cin>>s1>>s2;
    rpe(i,s1.size()-1,0) a.push_back(s1[i]-'0');
    rpe(i,s2.size()-1,0) b.push_back(s2[i]-'0');
    if(cmp(a,b)) c=sub(a,b);
    else cout<<'-',c=sub(b,a);
    rpe(i,c.size()-1,0) cout<<c[i];
    return 0;
}

 793. 高精度乘法 - AcWing题库

#include<bits/stdc++.h>
#define rep(i,a,b)  for(int i=a;i<=b;i++)
#define rpe(j,b,a)  for(int j=b;j>=a;j--)
using namespace std;
vector<int> mul(vector<int>&a,int b){
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size()||t;i++){
        if(i<a.size()) t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    while(c.back()==0&&c.size()>1) c.pop_back();
    return c;
}
int main(){
    string s1;
    int b;
    vector<int> a;
    cin>>s1>>b;
    rpe(i,s1.size()-1,0) a.push_back(s1[i]-'0');
    auto c=mul(a,b);
    rpe(i,c.size()-1,0) cout<<c[i];
    return 0;
}

794. 高精度除法 - AcWing题库

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rpe(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
vector<int> div(vector<int>a,int b,int &r){
    vector<int> c;
    r=0;
    rpe(i,a.size()-1,0){
        r=r*10+a[i];
        c.push_back(r/b);
        r=r%b;
    }
    reverse(c.begin(),c.end());
    while(c.back()==0&&c.size()>1) c.pop_back();
    return c;
}
int main(){
    string s;
    int b,r;
    vector<int> a;
    cin>>s>>b;
    rpe(i,s.size()-1,0) a.push_back(s[i]-'0');
    auto c=div(a,b,r);
    rpe(i,c.size()-1,0) cout<<c[i];
    cout<<endl<<r;
    return 0;
}