高精度入门（神犇请绕道）

· · 算法·理论

神犇请请来此

蒟蒻们好，今天我来讲高精度了。

为什么要有高精度

首先你们平时做运算是不是这样： 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b<<" "<<a-b<<" "<<a*b<<" "<<a/b<<" "<<a%b;
    return 0;
}

如果你们这样做，可以试一下这道题，如果你用C++里的整数运算，只能拿到部分(40)分,为什么会这样？ 原来，C++中编译器对整数的运算的支持最高到long long(64位，约为十进制1e18)，部分编译器可以做到int128(128位，约为十进制1e39，需手动定义且不能输入输出)，而有些题目的数据比1e39还大，这时就需要高精度了。

高精度模板

高精度的实现方式类似于我们小学学过的竖式，一位一位的加，遇到大于十的情况就进位，比较主流的方式是用C++的string(不会的可以自学一下字符串)。
你们最喜欢的代码来啦！ 

#include<bits/stdc++.h>
using namespace std;
int a[1005],b[1005],c[1005];
int main()
{
    string as,bs;
    cin>>as>>bs;
    reverse(as.begin(),as.end());//这里的reverse是反转函数，作用是将字符串反转，这里之所以要反转是因为要模拟竖式；如123和45，第一个字符串下标0是1，但45与123的位数不同，所以导致了5与3的下标不同，无法进行加减，反转后就不会有这个问题 
    reverse(bs.begin(),bs.end());
    for(int i=0;i<as.size();i++)
    {
        a[i]=as[i]-'0';//把字符变成数字（这里亦可减48），自行了解ASCII码 
    }
    for(int i=0;i<bs.size();i++)
    {
        b[i]=bs[i]-'0';
    }
    for(int i=0;i<=1000;i++)
    {
        c[i]=a[i]+b[i];//数组模拟竖式加法 
    }
    for(int i=0;i<=1000;i++)
    {
        if(c[i]>=10)//如果大于十了就进位 
        {
            c[i+1]++;
            c[i]-=10;
        }
    }
    int s=1000;//这里位数最多到500，我做的加强版位数到一千 
    while(c[s]==0&&s>0)
    {
        s--;//防止输出前导零 
    }
    for(int i=s;i>=0;i--)
    {
        cout<<c[i];//倒序输出结果 
    }
    return 0;
}

同样的道理， 我们也可以做出乘法的高精度：
高精度乘高精度： 

#include<bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005],c[1000005];
int main()
{
    string as,bs;
    cin>>as>>bs;
    reverse(as.begin(),as.end());//前面讲过了，这里就不再赘述 
    reverse(bs.begin(),bs.end());
    for(int i=0;i<as.size();i++)
    {
        a[i]=as[i]-'0';
    }
    for(int i=0;i<bs.size();i++)
    {
        b[i]=bs[i]-'0';
    }
    for(int i=0;i<as.size();i++)
    {
        for(int j=0;j<=bs.size();j++)
        {
            c[i+j]+=a[i]*b[j];//模拟竖式 
        }
    }
    for(int i=0;i<=3000;i++)
    {
        if(c[i]>=10)//如果大于十了就进位 
        {
            c[i+1]+=c[i]/10;//这里用+=是因为有时乘法不止进一位 
            c[i]%=10;
        }
    }
    int s=30000;
    while(c[s]==0&&s>0)
    {
        s--;
    }
    for(int i=s;i>=0;i--)
    {
        cout<<c[i];
    }
    return 0;
}

高精度乘低精度： 

#include<bits/stdc++.h>
using namespace std;
int a[3005],c[3005];
int main()
{
    string as;
    cin>>as;
    int b;//因为数值不大，用int就能存下 
    cin>>b;
    reverse(as.begin(),as.end());
    for(int i=0;i<as.size();i++)
    {
        a[i]=as[i]-'0';
    }
    for(int i=0;i<=3000;i++)
    {
        c[i]=b*a[i];//模拟竖式 
    }
    for(int i=0;i<=3000;i++)
    {
        if(c[i]>=10)
        {
            c[i+1]+=c[i]/10;
            c[i]%=10;
        }
    }
    int s=3000;
    while(c[s]==0&&s>0)
    {
        s--;
    }
    for(int i=s;i>=0;i--)
    {
        cout<<c[i];
    }
    return 0;
}

减法： 

#include <bits/stdc++.h>
using namespace std;
int a[10010],b[10010],c[10010];
string s1,s2;
bool cmp(string s1,string s2)
{
    if(s1.size()!=s2.size()) return s1.size()<s2.size();//这么做是防止小于零溢出 
    else return s1<s2;
}
int main()
{
    cin >> s1 >> s2;
    if(cmp(s1,s2))
    {
        cout << "-";//如果第一个比第二个小就输出负号 
        swap(s1,s2);
    }
    int len = max(s1.size(),s2.size()) -1;//最大下标
    int l1 = s1.size()-1;
    int l2 = s2.size()-1;
    for(int i=0;i<=l1;i++) a[i] = s1[l1-i] - '0';
    for(int i=0;i<=l2;i++) b[i] = s2[l2-i] - '0';
    for(int i=0;i<=len;i++){
        c[i] += a[i]-b[i];
        if(c[i]<0)// 借一当十 
        {
            c[i] += 10; 
            c[i+1] -= 1;
        } 
    }
    while(len>0&&c[len]==0) len--;
    for(int i=len;i>=0;i--) cout << c[i];
    return 0;
}

高精度除法： 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int T = 1e5+5;
int na[T], nb[T];
bool check(string a, string b);//先声明后定义 
string sub(string a, string b);
int main(){
    string a, b;
    cin >> a >> b;
    int lena = a.size(), lenb = b.size();

    string q, r;
    for (int i = 0; i < lena; i++){
        r.push_back(a[i]);//字符串操作，将一个符号 从尾部放入string 
        int idx = 0;
        while(idx < r.size()-1 && r[idx] == '0') idx++;
        r = r.substr(idx);//去前导0，substr截取字串 

        int cnt = 0;
        while(check(r, b)){
            r = sub(r, b);
            cnt++;
        }
        q += cnt + '0';
    }

    //去商的前导0
    int i = 0, lenq = q.size();
    while(i < lenq-1 && q[i] == '0') i++;
    //输出商和余数
    for(; i < lenq; i++) cout << q[i];
    cout << endl;

    int lenr = r.size();
    for (int i = 0; i < lenr; i++) cout << r[i];
    return 0;
}//此题需输出商和余数，需要求商或余数的请自行截取 
bool check(string a, string b){
    int lenb = b.size();
    if(a.size() != b.size()) return a.size() > b.size();
    else{
        for (int i = 0; i < lenb; i++){
            if(a[i] != b[i]) return a[i] > b[i];
        }
    }
    return true;
}

string sub(string a, string b){
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int lena = a.size();
    string c;
    int t = 0;
    for (int i = 0; i < lena; i++){
        char bi = (i < b.size()) ? b[i] : '0';//三目运算符，不会的自行学习 
        int x = a[i] - bi - t;
        if(x < 0){
            x += 10;
            t = 1;
        }else t = 0;
        c += x + '0';
    }
    int lenc = c.size();
    while(lenc > 1 && c[lenc-1] == '0') lenc--;
    c = c.substr(0, lenc);
    reverse(c.begin(), c.end());
    return c;
}

::::info[小练习] 例题
附加题一
附加题二
附加题三
神犇题（蒟蒻误入） ::::
~不要脸的求点赞和关注~
版权声明：一些信息出自此帖。