大数模板(加减乘除取模开方)

不带小数的大数：

struct BigInteger
{
    int len;
    int arg[1005];
    BigInteger(int x = 0){
        IntToBigInteger(x);
    }
    BigInteger(char *str){
        CharToBigInteger(str);
    }
    void print()
    {
        for (int i = len - 1; i >= 0; i--){
            cout<<arg[i];
        }
        cout<<endl;
    }
    void CharToBigInteger(char *str)
    {
        len = strlen(str);
        memset(arg, 0,sizeof(arg));
        for (int i = 0; i < len; i++){
            arg[i] = str[len - i - 1] - 48;
        }
        while(len > 0 && arg[len-1] == 0){
            len--;
        }
    }
    void IntToBigInteger(int x)
    {
        len = 0;
        memset(arg,sizeof(arg));
        do{
            arg[len++] = x % 10;
            x = x / 10;
        }while (x);
    }
    friend istream &operator>>(istream &in,BigInteger &w)
    {
        char str[1005];
        in>>str;
        w.CharToBigInteger(str);
        return in;
    }
    friend ostream& operator<<(ostream &out,BigInteger w)
    {
        for (int i = w.len - 1; i >= 0; i--){
            out<<w.arg[i];
        }
        return out;
    }
    friend bool operator==(BigInteger r,BigInteger w)
    {
        if (r.len != w.len) return false;
        int i = r.len - 1;
        while (i >= 0){
            if (r.arg[i] != w.arg[i])
                return false;
            i--;
        }
        return true;
    }
    friend bool operator<=(BigInteger r,BigInteger w)
    {
        if (r.len < w.len) return true;
        else if (w.len < r.len) return false;
        int i = r.len - 1;
        while (i >= 0){
            if (r.arg[i]<w.arg[i])
                return true;
            else if (r.arg[i]>w.arg[i])
                return false;
            i--;
        }
        return true;
    }
    friend bool operator<=(int x,BigInteger w)
    {
        BigInteger r;
        r.IntToBigInteger(x);
        if (r.len < w.len) return true;
        else if (w.len < r.len) return false;
        int i = r.len - 1;
        while (i >= 0){
            if (r.arg[i]<w.arg[i])
                return true;
            else if (r.arg[i]>w.arg[i])
                return false;
            i--;
        }
        return true;
    }
    friend bool operator<(BigInteger r,BigInteger w)
    {
        if (r.len < w.len) return true;
        else if (w.len < r.len) return false;
        int i = r.len - 1;
        while (i >= 0){
            if (r.arg[i]<w.arg[i])
                return true;
            else if (r.arg[i]>w.arg[i])
                return false;
            i--;
        }
        return false;
    }
    friend bool operator<(int x,BigInteger w)
    {
        BigInteger r;
        r.IntToBigInteger(x);
        if (r.len < w.len) return true;
        else if (w.len < r.len)    return false;
        int i = r.len - 1;
        while (i >= 0){
            if (r.arg[i]<w.arg[i])
                return true;
            else if (r.arg[i]>w.arg[i])
                return false;
            i--;
        }
        return false;
    }
    friend BigInteger operator+(int r,BigInteger w){
        w.arg[0] += r;
        int i = 0;
        while (w.arg[i] >= 10){
            w.arg[i + 1] += w.arg[i] / 10;
            w.arg[i] = w.arg[i] % 10;
            i++;
        }
        if(w.arg[i]) i++;
        w.len = i > w.len ? i : w.len;
        return w;
    }
    friend BigInteger operator+(BigInteger w,int r)
    {
        w.arg[0] += r;
        int i = 0;
        while (w.arg[i] >= 10){
            w.arg[i + 1] += w.arg[i] / 10;
            w.arg[i] = w.arg[i] % 10;
            i++;
        }
        if(w.arg[i]) i++;
        w.len = i > w.len ? i : w.len;
        return w;
    }
    friend BigInteger operator+(BigInteger r,BigInteger w)
    {
        int len = r.len > w.len ? r.len : w.len;
        for (int i = 0; i < len; i++){
            if(i < w.len)
                r.arg[i] = r.arg[i] + w.arg[i];
            r.arg[i + 1] += r.arg[i] / 10;
            r.arg[i] = r.arg[i] % 10;
        }
        while (r.arg[len] >= 10){
            r.arg[len + 1] += r.arg[len] / 10;
            r.arg[len] = r.arg[len] % 10;
            len++;
        }
        if(r.arg[len]) len++;
        r.len  = len > r.len ? len : r.len;
        return r;
    }
    friend BigInteger operator-(BigInteger r,BigInteger w)
    {
        for (int i = 0; i < r.len; i++){
            if (r.arg[i] >= w.arg[i])
                r.arg[i] = r.arg[i] - w.arg[i];
            else{
                r.arg[i] = r.arg[i] + 10;
                r.arg[i + 1] = r.arg[i + 1] - 1;
                r.arg[i] = r.arg[i] - w.arg[i];
            }
        }
        while (r.arg[r.len - 1] == 0 && r.len > 1)
            r.len--;
        return r;
    }
    friend BigInteger operator-(BigInteger r,int w)
    {
        for (int i = 0; i < r.len; i++,w = w / 10){
            if (r.arg[i] >= w % 10)
                r.arg[i] = r.arg[i] - w % 10;
            else{
                r.arg[i] = r.arg[i] + 10;
                r.arg[i + 1] = r.arg[i + 1] - 1;
                r.arg[i] = r.arg[i] - w % 10;
            }
        }
        while (r.arg[r.len - 1] == 0 && r.len > 1)
            r.len--;
        return r;
    }
    friend BigInteger operator*(int x,BigInteger w)
    {
        BigInteger r;
        if(x == 0 || (w.len == 1 && w.arg[0] == 0)){
            return r;
        }
        for (int i = 0; i < w.len; i++){
            r.arg[i] += w.arg[i] * x;
            r.arg[i + 1] += r.arg[i] / 10;
            r.arg[i] = r.arg[i] % 10;
        }
        int i = r.arg[w.len] == 0 ? w.len-1 : w.len;
        while (r.arg[i] >= 10){
            r.arg[i + 1] = r.arg[i] / 10;
            r.arg[i] = r.arg[i] % 10;
            i++;
        }
        r.len = (i >= 0) ? i + 1 : 1;
        return r;
    }
    friend BigInteger operator*(BigInteger w,int x)
    {
        BigInteger r;
        if(x == 0 || (w.len == 1 && w.arg[0] == 0)){
            return r;
        }
        for (int i = 0; i < w.len; i++){
            r.arg[i] += w.arg[i] * x;
            r.arg[i + 1] += r.arg[i] / 10;
            r.arg[i] = r.arg[i] % 10;
        }
        int i = r.arg[w.len] == 0 ? w.len-1 : w.len;
        while (r.arg[i] >= 10){
            r.arg[i + 1] = r.arg[i] / 10;
            r.arg[i] = r.arg[i] % 10;
            i++;
        }
        r.len = (i >= 0) ? i + 1 : 1;
        return r;
    }
    friend BigInteger operator*(BigInteger r,BigInteger w)
    {
        BigInteger v;
        if((r.len == 1 && r.arg[0] == 0)|| (w.len == 1 && w.arg[0] == 0)){
            return v;
        }
        for (int i = 0; i < r.len; i++){
            for (int k = 0; k < w.len; k++){
                v.arg[i + k] += w.arg[k] * r.arg[i];
                v.arg[i + k + 1] += v.arg[i + k] / 10;
                v.arg[i + k] = v.arg[i + k] % 10;
            }
        }
        int i = w.len + r.len - 1;
        i = v.arg[i] == 0 ? i-1 : i;
        while (v.arg[i] >= 10){
            v.arg[i + 1] = v.arg[i] / 10;
            v.arg[i] = v.arg[i] % 10;
            i++;
        }
        v.len = (i >= 0) ? i + 1 : 1;
        return v;
    }

    friend BigInteger operator/(BigInteger r,int w)
    {
        BigInteger  h,resl;
        if(w == 0) return h;
        for (int i = r.len - 1; i >= 0; i--){
            resl = 10 * resl;
            h = r.arg[i] + (10 * h);
            while (w <= h){
                resl = 1 + resl;
                h = h - w;
            }
        }
        return resl;
    }
    friend BigInteger operator/(BigInteger r,BigInteger w)
    {
        BigInteger h,resl;
        if(w.len == 1 && w.arg[0] == 0) return h;
        for (int i = r.len - 1; i >= 0; i--){
            resl = 10 * resl;
            h = r.arg[i] + (10 * h);
            while (w <= h){
                resl = 1 + resl;
                h = h - w;
            }
        }
        return resl;
    }

    friend BigInteger operator%(BigInteger r,BigInteger w)
    {
        BigInteger h;
        if(w.len == 1 && w.arg[0] == 0) return h;
        for (int i = r.len - 1; i >= 0; i--){
            h = r.arg[i] + (10 * h);
            while (w <= h){
                h = h - w;
            }
        }
        return h;
    }
    void sqrt()
    {
        BigInteger w,r;
        w.len = r.len = 0;
        int lens = len - 1;
        if(len == 1 && arg[0] == 1)
            return ;
        r.arg[r.len++] = arg[lens--];
        if (len % 2 == 0)
            r = arg[lens--] + 10 * r;
        while (lens >= -1){
            int i = 0;
            while ((i*(i + 20 * w)) <= r){
                i++;
            }
            i--;
            if (i == -1 || (r.len == 1 && r.arg[0] == 1))
                i = 0;
            r = r - (i*(i + 20 * w));
            w = i + 10 * w;
            if(lens >= 0){
                r = arg[lens--] + 10 * r;
                r = arg[lens--] + 10 * r;
            }
            else
                lens -= 2;
        }
        *this = w;
    }
};

带小数的大数模板：

struct BigDecimal{
    BigDecimal(int x){
        IntToBigDecimal(x);
    }
    BigDecimal(char *str = "0"){
        CharToBigDecimal(str);
    }
    int arg[1005];
    int len,point;//长度，小数位数
    void print()
    {
        for(int i = len-1; i >= 0; i--){
            cout<<arg[i];
            if(i == point && i)
                cout<<".";
        }
        cout<<endl;
    }
    void Clear()
    {
        int k = 0;
        while(point > 0 && arg[k] == 0)
            point--,k++;
        if(k == 0)
            return ;
        BigDecimal w;
        w.len = len - k;
        w.point = point;
        for(int i = 0; i < w.len; i++){
            w.arg[i] = arg[i+k];
        }
        *this = w;
    }
    void CharToBigDecimal(char *str)
    {
        int k = -1,flag = 0;
        point = 0;
        len = strlen(str);
        memset(arg,sizeof(arg));
        while(++k < len){
            if(str[len-k-1] == '.'){
                point = k;
                flag = 1;
            }
            else{
                arg[k-flag] = str[len-k-1]-48;
            }
        }
        if(point != len-1)
            len = len - flag;
        while(len > point+1 && arg[len-1] == 0)
            len--;
        Clear();
    }
    void IntToBigDecimal(int x)
    {
        len = 0;
        point = 0;
        memset(arg,sizeof(arg));
        do{
            arg[len++] = x % 10;
            x = x / 10;
        }while (x);
    }
    void Aligning(int cheap)
    {
        BigDecimal v;
        v.len = len - cheap;
        v.point = point - cheap;
        while(len--){
            v.arg[len-cheap] = arg[len];
        }
        *this = v;
    }
    friend bool operator<=(BigDecimal r,BigDecimal w)
    {
        if(r.len - r.point > w.len - w.point)
            return false;
        else if(r.len - r.point < w.len - w.point)
            return true;
        if(r.point < w.point){
            r.Aligning(r.point - w.point);
        }
        if(w.point > w.point){
            w.Aligning(w.point - r.point);
        }
        for(int i = r.len - 1; i >= 0; i--){
            if(r.arg[i] < w.arg[i]) return true;
            if(r.arg[i] > w.arg[i]) return false;
        }
        return true;
    }
    friend BigDecimal operator+(BigDecimal r,BigDecimal w)
    {
        if(r.point < w.point)
            swap(r,w);
        int cheap = r.point-w.point;
        int len = r.len > w.len+cheap ? r.len : w.len+cheap;
        for(int i = 0; i < len ; i++){
            if(i-cheap >= 0)
                r.arg[i] = r.arg[i] + w.arg[i-cheap];
            r.arg[i+1] += r.arg[i]/10;
            r.arg[i] = r.arg[i]%10;
        }
        while(r.arg[len] >= 10){
            r.arg[len+1] += r.arg[len]/10;
            r.arg[len] = r.arg[len]%10;
        }
        r.len = r.arg[len] == 0 ? len : len+1;
        r.Clear();
        return r;
    }
    friend BigDecimal operator+(int x,BigDecimal w){
        BigDecimal r(x);
        return r + w;
    }
    friend BigDecimal operator+(BigDecimal w,int x){
        BigDecimal r(x);
        return r + w;
    }
    friend BigDecimal operator-(BigDecimal r,BigDecimal w)
    {
        int cheap = r.point - w.point;
        if(cheap < 0){
            r.Aligning(cheap);
            cheap = 0;
        }
        for (int i = 0; i < r.len; i++){
            if (i - cheap >= 0 && r.arg[i] >= w.arg[i-cheap])
                r.arg[i] = r.arg[i] - w.arg[i-cheap];
            else if(i - cheap >= 0){
                r.arg[i] = r.arg[i] + 10;
                r.arg[i + 1] = r.arg[i + 1] - 1;
                r.arg[i] = r.arg[i] - w.arg[i-cheap];
            }
        }
        while (r.len - 1 > r.point && r.arg[r.len - 1] == 0)
            r.len--;
        r.Clear();
        return r;
    }
    friend BigDecimal operator-(BigDecimal w,int x){
        BigDecimal r(x);
        return r - w;
    }
    friend BigDecimal operator*(BigDecimal r,BigDecimal w)
    {
        BigDecimal v;
        if((r.len == 1 && r.arg[0] == 0)|| (w.len == 1 && w.arg[0] == 0)){
            return v;
        }
        v.point = r.point+w.point;
        for (int i = 0; i < r.len; i++){
            for (int k = 0; k < w.len; k++){
                v.arg[i + k] += w.arg[k] * r.arg[i];
                v.arg[i + k + 1] += v.arg[i + k] / 10;
                v.arg[i + k] = v.arg[i + k] % 10;
            }
        }
        int i = w.len + r.len - 1;
        i = v.arg[i] == 0 ? i-1 : i;
        while (v.arg[i] >= 10){
            v.arg[i + 1] = v.arg[i] / 10;
            v.arg[i] = v.arg[i] % 10;
            i++;
        }
        v.len = (i >= 0) ? i + 1 : 1;
        v.Clear();
        return v;
    }
    friend BigDecimal operator*(int x,BigDecimal w){
        BigDecimal r(x);
        return r * w;
    }
    friend BigDecimal operator*(BigDecimal w,int x){
        BigDecimal r(x);
        return r * w;
    }
    friend BigDecimal operator/(BigDecimal r,BigDecimal w)
    {
        BigDecimal h,resl;
        int len = r.point > w.point ? r.point : w.point;
        for(int i = 0; i < len; i++){
            r = r * 10;
        }
        r = r * 100000000;
        if(w.len == 1 && w.arg[0] == 0) return resl;
        for (int i = r.len - 1; i >= 0; i--){
            resl = 10 * resl;
            h = r.arg[i] + (10 * h);
            while (w <= h){
                resl = 1 + resl;
                h = h - w;
            }
        }
        resl.point = len + 8;
        resl.Clear();
        return resl;
    }
    friend BigDecimal operator/(BigDecimal w,int x){
        BigDecimal r(x);
        return r / w;
    }
    BigDecimal sqrt()
    {
        int cheap = point;
        while(point > 0){
            point -= 2;
        }
        if(point == -1){
            point = 0;
            *this = *this * 10;
        }
        *this = (*this) * 100000000;
        int lens = len - 1;
        if(len == 1 && arg[0] == 1)
            return *this;
        BigDecimal w,r;
        w.len = r.len = 0;
        r.arg[r.len++] = arg[lens--];
        if (len % 2 == 0)
            r = arg[lens--] + 10 * r;
        while (lens >= -1){
            int i = 0;
            while ((i*(i + 20 * w)) <= r){
                i++;
            }
            i--;
            if (i == -1 || (r.len == 1 && r.arg[0] == 1))
                i = 0;
            r = r - (i*(i + 20 * w));
            w = i + 10 * w;
            if(lens >= 0){
                r = arg[lens--] + 10 * r;
                r = arg[lens--] + 10 * r;
            }
            else
                lens -= 2;
        }
        w.point += (4 + (cheap +1 ) / 2);
        w.Clear();
        return w;
    }
};