【算法笔记】高精度

什么是高精度

嗯，高精度就是精度很高（滚粗）

好切入正题，高精度就是因为C艹的自带整数类型最大只有64位的long long，无法应对某些无聊出题人出的超大数据。而double的有效数字位数太低，无法精确运算，因此只能使用高精度。

高精度的原理就是使用数组来模拟每一位上的数字。至于数组的选择，可以使用char数组，也可以使用string或vector，看个人喜好。一般来说，char跑的是最快的。

当然也可以将高精整数封装成一个类，再加上重载运算符等高端操作来增强代码的可（复）读（杂）性，并且方便copy模板。

什么时候用高精

嗯，当遇到计算阶乘，斐波那契等飞速增长的东西的时候如果unsigned long long还是不能解决问题的话，就上高精。还有当数据非常大的时候也考虑使用高精。

遇到诸如a_i\leq 10^{10000}这种数据范围，就肯定不用说了。。。。。。

高精的实现

大体思路

大体的思路还是使用字符数组或者vector来存储。然后进行计算时就参照竖式计算来算即可。

存储的时候下标0处存储个位，下标1存储十位，依次从低位向高位存储，方便竖式的计算。

当然还有很多神奇的方法能加速乘除法的运算，比如FFT可以加速高精乘法。但由于我不会所以这里就不讲了，

加法

加法的实现很简单，只需要模仿竖式计算一样进位就可以了。下面来模拟一下12345+678的过程来弄懂代码的思路

 12345
+  678

首先从最右边开始，进行相加，5+8=13，填上3并向上一位进1

 12345
+  678
------
     3           进1

然后到十位，4+7=11，再加上前面进的1等于12，填上2并进一

 12345
+  678
------
    23           进1

然后到百位，3+6+1=10，填上0，进1

 12345
+  678
------
   023           进1

接下来到了千位。发现下面的数字并没有千位，怎么办呢，这就需要在一开始的时候补0以避免一些玄学的错误（如果你使用STL容器的话）2+0+1=3，填上3，进0

 12345
+  678
------
  3023           进0

最后同理，加完就好了，最终答案是13023。完结撒花。高精加法的原理大概就是这样的，复杂度为O(n)。

如果使用字符数组来存储的话，画风大概是这样的，写的时候一定记得-'0'：

#include <cstring>
#include <cstdio>
#define max(a,b) (a>b?a:b)

const int maxn=505;
char a[maxn],b[maxn],aa[maxn],bb[maxn];
int ans[maxn];

int main()
{
    memset(a,'0',sizeof(a));
    memset(b,'0',sizeof(b));
    scanf("%s %s",aa,bb);
    for(int i=0;i<strlen(aa);i++)
        a[strlen(aa)-1-i]=aa[i];
    for(int i=0;i<strlen(bb);i++)
        b[strlen(bb)-1-i]=bb[i];
    int tmp=0;//存储进的位
    int l=max(strlen(aa),strlen(bb));
    for(int i=0;i<l;i++)
    {
        ans[i]=(a[i]-'0'+b[i]-'0'+tmp)%10;
        tmp=(a[i]-'0'+b[i]-'0'+tmp)/10;
    }
    if(tmp)//如果最后还进有一位
        printf("%d",tmp);//直接输出他
    for(int i=l-1;i>=0;i--)
        printf("%d",ans[i]);//逆序输出
    return 0;
}

嗯，真香，又短又跑得快。

当然这只是最简单的情况，不用考虑负数等等乱七八糟的东西，也不用进行什么复杂的操作，但如果操作变得复杂，就有必要将其封装成一个结构体或者类并重载运算符以减少出错的概率。

减法

减法的实现也很简单，跟加法没什么本质的区别，只不过进位变成了退位。退的时候只需要在前面一位减去1就可以了，然后将减出来的负值加上10。

但是细节还是有的，比如你可能需要判断两数的大小并加上负数。而且输出的时候要去掉前导零，例如10000-9999，不正确的方法会输出00001，然后就会被判错。所以高精实现的麻烦之处就在于细节。

#include <iostream>
#include <string>
#include <algorithm>
#define mian main
#define MAXN 10500
using namespace std;

bool cmp_minus(string a, string b)
{
    if (a.length() != b.length())
        return a.length() > b.length();
    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] != b[i])
            return a[i] > b[i];
    }
}

string _minus(string a, string b)
{
    if(a==b) return "0";
    bool flag = cmp_minus(a, b);
    if (!flag)
        swap(a, b);
    short an[MAXN] = {0}, bn[MAXN] = {0};
    short len1 = a.length(), len2 = b.length();
    short maxl = max(len1, len2);
    for (int i = 0; i < len1; i++)
        an[i] = a[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        bn[i] = b[len2 - i - 1] - '0';
    string ans1;
    int tmp = 0;
    for (int i = 0; i < maxl; i++)
    {
        tmp = an[i] - bn[i];
        if (tmp < 0)
        {
            tmp += 10;
            an[i + 1]--;
        }
        ans1=char(tmp+'0')+ans1;
    }
    short head=0;
    while(ans1[head]=='0') head++;
    string ans(ans1,head);
    if(!flag) ans="-"+ans;
    return ans;
}

int mian()
{
    string a, b;
    cin >> a >> b;
    cout << _minus(a, b);
    return 0;
}

由于用char数组太麻烦了所以这里用了string

乘法

乘法也是像竖式一样乘，先乘后加，由于对于每一位都要进行乘法，所以复杂度为O(n^2)。当然FFT可以优化到log级别但我不会。所以这里用朴素的高精乘法。

想打出乘法，首先要学会加法，因为最后需要加起来。

接下来模拟12345*678的过程以加强理解

 12345
*  678

首先要将12345*8，过程与加法的类似，都要记录进的位。

 12345
*  678
------
 98760

然后将12345*7，注意如果最高位还有进位的话要处理干净，然后注意提前补0方便最后相加。

 12345
*  678
------
 98760
864150//补0

最后

  12345
 *  678
-------
  98760
 864150
7407000//补0

再最后按照高精加法的方式加起来，当然这个过程可以每乘一位进行一次

  12345
 *  678
-------
  98760
 864150
7407000//补0
-------
8369910

其实，乘法处理的方式与加法的很像，但是同样要注意最后去掉前导0，还有如果其中一个数是0，那就直接输出0就可以了。

下面的类是重载了乘号运算符的：

struct bigint
{
    vector<int> v;
}

bigint operator*(const bigint &a,const bigint &b)//重载运算符
{
    if((a.v.size()==1&&a.v[0]==0)||(b.v.size()==1&&b.v[0]==0))//如果其中一个是0
        return bigint(vector<int>(1),0);//直接返回
    vector<int> aa=a.v,bb=b.v;
    if(a<b)
        swap(aa,bb);//看似可以减小乘的次数
    bigint ans;
    for(int j=0;j<bb.size();j++)//模拟
    {
        int tmp=0;
        bigint ans1;
        for(int i=0;i<j;i++)//提前补0
            ans1.v.push_back(0);
        for(int i=0;i<aa.size();i++)//然后模拟乘法
        {
            ans1.v.push_back((aa[i]*bb[j]+tmp)%10);
            tmp=(aa[i]*bb[j]+tmp)/10;
        }
        if(tmp)//如果还有剩下的进位
            ans1.v.push_back(tmp);//补进去
        ans=ans+ans1;//更新答案
    }
    return ans;
}

除法

除法是一个很玄学的东西，因为这玩意真的不好模拟竖式的计算。

一个不错的方法是累着相减，减到0为止，然后输出答案即可。

但是这种复杂度完全就是玄学，因为最后花的时间完全取决于商的大小，如果商很大，就意味着要除很多次，这样的话消耗非常大。

这里已经重载了-=运算符和>运算符

bigint operator/(const bigint &a, const bigint &b)
{
    bool flag=0;
    if(a.symbol!=b.symbol)
        flag=1;
    bigint aa=bigint(a,0),bb=bigint(b,0);
    if(aa<bb)
        return bigint(vector<int>(1),flag);
    bigint zero=bigint(vector<int>(1),0);
    bigint ans;
    while(aa>zero)
    {
        aa-=bb;
        if(!(aa>zero))
            break;
        ans++;
    }
    return bigint(ans,flag);
}

自用板子

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
#include <iostream>
#define R register
using namespace std;

struct bigint
{
    vector<int> v;
    bool symbol;
    int size()
    {
        return v.size();
    }
    bigint(vector<int> vv)
    {
        this->v=vv;
    }
    bigint(vector<int> vv,bool symbol)
    { 
        this->v=vv;
        this->symbol=symbol;
    }
    bigint(bigint a,bool symbol)
    {
        this->v=a.v;
        this->symbol=symbol;
    }
    bigint()
    {
        symbol=0;
    }
    void operator=(const bigint &a)
    { 
        this->v=a.v;
        this->symbol=a.symbol;
    }
    friend bool operator<(const bigint&,const bigint&);
    friend bool operator>(const bigint&,const bigint&);
    friend bool operator==(const bigint&,const bigint&);
    friend bool operator!=(const bigint&,const bigint&);
    friend bigint operator+(const bigint&,const bigint&);
    friend bigint operator-(const bigint&,const bigint&);
    friend bigint operator*(const bigint&,const bigint&);
    friend bigint operator/(const bigint&,const bigint&);
    friend ostream& operator<<(ostream&,const bigint&);
    bigint operator-=(const bigint &a)
    {
        *this=*this-a;
        return *this;
    }
    bigint operator+=(const bigint &a)
    {
        *this=*this+a;
        return *this;
    }
    bigint operator*=(const bigint &a)
    {
        *this=(*this)*a;
        return *this;
    }
    bigint operator/=(const bigint &a)
    {
        *this=(*this)/a;
        return *this;
    }
    bigint operator++(int)
    {
        vector<int> one={1};
        bigint a=*this;
        *this+=bigint(one,0);
        return a;
    }
    bigint operator++()
    {
        vector<int> one={1};
        *this+=bigint(one,0);
        return *this;
    }
    bigint operator--(int)
    {
        vector<int> one={1};
        bigint a=*this;
        *this-=bigint(one,0);
        return a;
    }
    bigint operator--()
    {
        vector<int> one={1};
        *this-=bigint(one,0);
        return *this;
    }
};

bigint conv(int a)
{
    bool flag=a<0;
    a=a>=0?a:-a;
    vector<int> v;
    while(a)
    {
        v.push_back(a%10);
        a/=10;
    }
    return bigint(v,flag);
}

bool operator<(const bigint &a, const bigint &b)
{
    if(a.symbol^b.symbol)
        return a.symbol;
    if(a.v.size()!=b.v.size())
        return a.symbol?a.v.size()>b.v.size():a.v.size()<b.v.size();
    for(R int i=a.v.size()-1;i>=0;i--)
        if(a.v[i]!=b.v[i])
            return a.symbol?a.v[i]>b.v[i]:a.v[i]<b.v[i];
    return false;
}

bool operator==(const bigint &a,const bigint &b)
{
    if(a.symbol!=b.symbol || a.v.size()!=b.v.size())
        return false;
    for(R int i=0;i<a.v.size();i++)
        if(a.v[i]!=b.v[i])
            return false;
    return true;
}

bool operator!=(const bigint &a, const bigint &b)
{
    if(a.symbol!=b.symbol || a.v.size()!=b.v.size())
        return true;
    for(R int i=0;i<a.v.size();i++)
        if(a.v[i]!=b.v[i])
            return true;
    return false;
}

bool operator>(const bigint &a, const bigint &b)
{
    return a!=b&&b<a;
}

bool operator<=(const bigint &a, const bigint &b)
{
    return (a<b)||(a==b);
}

bool operator>=(const bigint &a,const bigint &b)
{
    return (a==b)||(b<a);
}

bigint operator+(const bigint &a,const bigint &b)
{
    bool flag;
    if(a.symbol&&(!b.symbol))
        return b-bigint(a,0);
    if(b.symbol&&(!a.symbol))
        return a-bigint(b,0);
    if(a.symbol==b.symbol)
        flag=a.symbol;
    vector<int> aa=a.v, bb=b.v;
    vector<int> ans;
    if(aa.size()>bb.size())
        swap(aa,bb);
    while(aa.size()<=bb.size())
        aa.push_back(0);
    int tmp=0;
    for(R int i=0;i<bb.size();i++)
    {
        ans.push_back((aa[i]+bb[i]+tmp)%10);
        tmp=(aa[i]+bb[i]+tmp)/10;
    }
    if(tmp)
        ans.push_back(tmp);
    return bigint(ans,flag);
}

bigint operator-(const bigint &a,const bigint &b)
{
    bool flag=0;
    if(a.symbol&&(!b.symbol))
        return a+bigint(b,1);
    if(b.symbol&&(!a.symbol))
        return bigint(b,0)+a;
    if(a.symbol==b.symbol)
        flag=a.symbol;
    vector<int> aa=a.v, bb=b.v;
    vector<int> ans;
    if(a<b)
        swap(aa,bb),flag=!flag;
    while(aa.size()>=bb.size())
        bb.push_back(0);
    for(R int i=0;i<aa.size();i++)
    {
        int tmp1=aa[i]-bb[i];
        if(tmp1<0)
        {
            aa[i+1]--;
            tmp1+=10;
        }
        ans.push_back(tmp1);
    }
    while(ans.size()>1&&ans[ans.size()-1]==0)
        ans.pop_back();
    return bigint(ans,flag);
}

bigint operator*(const bigint &a,const bigint &b)
{
    if((a.v.size()==1&&a.v[0]==0)||(b.v.size()==1&&b.v[0]==0))
        return bigint(vector<int>(1),0);
    bool flag=0;
    if(a.symbol!=b.symbol)
        flag=1;
    vector<int> aa=a.v,bb=b.v;
    if(a<b)
        swap(aa,bb);
    bigint ans;
    for(int j=0;j<bb.size();j++)
    {
        int tmp=0;
        bigint ans1;
        for(int i=0;i<j;i++)
            ans1.v.push_back(0);
        for(int i=0;i<aa.size();i++)
        {
            ans1.v.push_back((aa[i]*bb[j]+tmp)%10);
            tmp=(aa[i]*bb[j]+tmp)/10;
        }
        if(tmp)
            ans1.v.push_back(tmp);
        ans=ans+ans1;
    }
    return ans;
}

bigint operator/(const bigint &a, const bigint &b)
{
    bool flag=0;
    if(a.symbol!=b.symbol)
        flag=1;
    bigint aa=bigint(a,0),bb=bigint(b,0);
    if(aa<bb)
        return bigint(vector<int>(1),flag);
    bigint zero=bigint(vector<int>(1),0);
    bigint ans;
    while(aa>zero)
    {
        aa-=bb;
        if(!(aa>=zero))
            break;
        ans++;
    }
    return bigint(ans,flag);
}

bigint read()
{
    vector<int> v;
    int x;
    char c;
    bool flag=0;
    while(!isdigit(c))
    {
        if(c=='-')
            flag=1;
        c=getchar();
    }
    while(isdigit(c))
        v.push_back(c-'0'),c=getchar();
    reverse(v.begin(),v.end());
    return bigint(v,flag);
}

ostream& operator << (ostream &output,const bigint &a)
{
    vector<int> v=a.v;
    reverse(v.begin(),v.end());
    if(a.symbol)
        output<<'-';
    for(auto i:v)
        output<<i;
    return output;
}

int main()
{
    bigint a=read(),b=read();
    //do sth
    return 0;
}