同样搬以前初三写的。。。
其实还有个val.2,搬到文章里去了

@

在做一道斯特林数的时候被卡高精。。。于是滚来写一些简单的高精

高精构造

  • 这里使用结构体封装,方便使用
  • 尽量避免直接赋等,会加上个On复杂度
  • 所有函数如\(add(a,b)\)是在a上加b,a使用地址,速度较快

结构体

struct bigint{
    int length,num[maxn];
    bigint(){
        memset(num,0,sizeof(num));
        length=0;
    }
};

注意:length存0开始的位数,实际有效位数为0~length-1
构造函数能写就写

char数组转高精:

inline void change(char a[],bigint &b){
    b.length=strlen(a);
    for(int i=0;i<b.length;i++){
        b.num[i]=a[b.length-i-1]-'0';//注意要减去‘0’
    }
}

高精加高精

inline void add(bigint &a,bigint &b){
    int ll=max(a.length,b.length);
    int exd=0;
    for(int i=0;i<ll;i++){
        int tmp=a.num[i]+b.num[i]+exd;
        a.num[i]=tmp%10;
        exd=tmp/10;
    }
    a.length=ll;
    if(exd){
        a.num[ll]=exd;
        a.length++;
    }
}

变量维护进位,模拟即可

高精乘单精

inline void mul(bigint &a,int b){
    for(int i=0;i<a.length;i++){
        a.num[i]*=b;
    }
    for(int i=0;i<a.length;i++){
        a.num[i+1]+=a.num[i]/10;
        a.num[i]%=10;
    }//此时ai可能不止一位
    int m=a.num[a.length];
    while(m){
        a.num[(++a.length)-1]=m%10;
        m/=10;
    }//最高位长度处理
}

高精除单精

inline void div(bigint &a,int b){
    int d=0;
    for(int i=a.length-1;i>=0;i--){
        int tmp=d*10+a.num[i];
        a.num[i]=tmp/b;
        d=tmp%b;
    }
    while(a.num[a.length-1]==0){
        a.length--;
    } //去除高位0
}

高精和高精乘除与压位高精就之后再写吧 (

(咕

01-12 08:12