压位高精板子

/**-------------------------整数高精度-------------------------*/

///继承vector解决位数限制(当前最大位数是9倍整型最大值)，操作方便（注意size()返回无符号长整型，尽量不要直接把size放入表达式）
struct Huge_Int:vector{

    static const int WIDTH = 9;///压位数，压9位以下 比较安全
    static const long long BASE = 1e9;///单位基
    static const long long MAX_INT = ~(1<<31);///最大整型
    bool SIGN;

    ///初始化，同时也可以将低精度转高精度、字符串转高精度
    ///无需单独写高精度数和低精度数的运算函数，十分方便
    Huge_Int(long long n = 0){*this = n;}
    Huge_Int(const string &str){*this = str;}

    ///格式化，包括进位和去前导0，用的地方很多，先写一个
    Huge_Int & format(int fixlen = 1){//去0后长度必须大于等于fixlen，给乘法用的
        while(size()>fixlen && !back()) pop_back();//去除最高位可能存在的0
        if(!back()) SIGN = 0;
        for(int i=1; i=BASE)
        {
            push_back(back()/BASE);
            (*this)[size()-2]%=BASE;
        }//位外进位
        return *this;//为使用方便，将进位后的自身返回引用
    }

    ///归零
    void reset(){
        clear();
        SIGN = 0;
    }

    ///重载等于，初始化、赋值、输入都用得到
    Huge_Int operator=(long long n){
        reset();
        SIGN = n<0;
        if(SIGN) n = -n;
        push_back(n);
        format();
        return *this;
    }
    Huge_Int operator=(const string &str){
        reset();
        if(str.empty()) push_back(0);
        SIGN = str[0] == '-';
        for(int i = str.length() - 1;i>=0+SIGN;i-=WIDTH){
            long long tmp = 0;
            for(int j = max(i-WIDTH+1,0+SIGN);j<=i;j++)
                tmp = (tmp<<3) + (tmp<<1) + (str[j]^48);
            push_back(tmp);
        }
        format();
        return *this;
    }

    ///重载输入输出
    friend istream & operator>>(istream &is, Huge_Int &tmp){
        string str;
        if(!(is>>str)) return is;
        tmp = str;
        return is;
    }
    friend ostream & operator<<(ostream &os, const Huge_Int &tmp){
        if(tmp.empty()) os<<0;
        else{
            if(tmp.SIGN) os<<'-';
            os<=0;i--){
            os<b.size():a.size()=0; i--)
            if(a[i]!=b[i])return a.SIGN? a[i]>b[i] : a[i](const Huge_Int &a,const Huge_Int &b){return b=(const Huge_Int &a,const Huge_Int &b){return !(ab);}
    friend bool operator!=(const Huge_Int &a,const Huge_Int &b){return ai) a[j--]--,a[j]+=BASE;
            }
        }
        return a.format();
    }
    friend Huge_Int operator-(Huge_Int a,const Huge_Int &b){return a-=b;}
    friend Huge_Int & operator--(Huge_Int &a){return a-=1;}
    friend Huge_Int operator--(Huge_Int &a,int){
        Huge_Int old = a;
        --a;
        return old;
    }


    ///乘法，不能先实现*=，因为是类多项式相乘，每位都需要保留，不能覆盖
    friend Huge_Int operator*(const Huge_Int &a,const Huge_Int &b){
        Huge_Int n;
        n.SIGN = a.SIGN^b.SIGN;
        n.assign(a.size()+b.size()-1,0);//表示乘积后最少的位数(可能会被format消掉，因此添加了format参数)
        for(int i=0; i=0;i--) bl = bl * BASE + b[i];
            for(int i = ans.size()-1;i>=0;i--){
                rest *= BASE;
                ans[i] += rest;
                rest = ans[i]%bl;
                ans[i]/=bl;
            }
            a = a.SIGN?(-rest):rest;
            return ans.format();
        }
        else{
            ans.SIGN = a.SIGN^b.SIGN;
            for(int i=a.size()-b.size(); abs(a)>=abs(b); i--){//减法代替除法
                Huge_Int c,d;
                d.assign(i+1,0);
                d.back() = 1;
                d.SIGN = ans.SIGN;
                c=b*d;//提高除数位数进行减法
                while(abs(a)>=abs(c)) a-=c,ans+=d;
                d.pop_back();
                if(!d.empty()){//遍历压的位
                    d.back() = BASE/10;
                    for(int i = 1;i=abs(c)) a-=c,ans+=d;
                        d.back()/=10;
                    }
                }
            }
            return ans;
        }
    }
    friend Huge_Int operator/(Huge_Int a,const Huge_Int &b){return divmod(a,b);}
    friend Huge_Int & operator/=(Huge_Int &a,const Huge_Int &b){return a = a/b;}
    friend Huge_Int & operator%=(Huge_Int &a,const Huge_Int &b){return divmod(a,b),a;}
    friend Huge_Int operator%(Huge_Int a,const Huge_Int &b){return a%=b;}
};

/**-------------------------浮点高精度-------------------------*/