白书你好

看书啊看书啊看书啊！

买了小大白书的kindle版，所以用稍微零碎的时间来看小白书，其实一直在说要看完白书啊看完白书啊，其实一批了木有看完。当然，小白对于这个阶段意义不是太大了，把语言篇直接pase，从算法篇开始，再过一遍。

其实看书是个很快的过程，理解用的时间也不是太多，更多的时间是花在总结上，我发现我自从建了博客写学习总结，一个学习过程有1/3是看书理解，1/3是琢磨写总结。几乎和再看一遍用的时间一样。记得开始的时候写数据结构总结，一章就是两三小时。

其实还是很纠结要不要再用这么多时间写总结的，那些不写总结的家伙，看书就是快。都无奈了。

大数问题

大数问题是进集训队第一周狂刷的东西，挺练模拟能力的，不过今天我才发现白书是用结构体和运算符重载把大数搞定的，我便模仿一下，不用结构体，直接用类，写个大数类，以后直接当模板。

大数，就是特别大的数，因为，大到longlong存储不下去，便需要用数组存储，因此，需要用数组来模拟加减乘除，这次我只打算搞加减乘。

构建大数类

存储：

要有长度，保存大数的长度，在计算，打印，都很有必要

要有负号标记，在处理的时候，知道这是一个大负数

一个长数组，用来保存大整数

class bign
{
private:
    bool sign;
    int len;
    int num[MAX_LEN];
}

 非计算操作：

要有初始化，赋值，包括字符串赋值，int赋值等，本来想和白书一样重载=运算符，但是突然发现我这是在写一个类啊，不是结构体，那么直接重载构造函数就可以了，所以写了无参数，字符串参数，整型参数的构造函数。

可以打印，直接友元函数重载

class bign
{
public:
    bign(){len = 0;memset(num,0,sizeof(num));}
    bign(char *s)
    {
        sign = 0;
        int s_len = strlen(s);
        memset(num,0,sizeof(num));

        if(s[0] == '-')
        {
            sign = 1;
            int i = 0;
            len = s_len - 1;
            for(char *p = s + s_len - 1;p > s;p--)
                num[i++] = *p - '0';
        }else
        {
            int i = 0;
            len = s_len;
            for(char *p = s + s_len - 1;p >= s;p--)
                num[i++] = *p - '0';
        }

    }
    bign(int n)
    {
        len = 0;
        sign = 0;
        memset(num,0,sizeof(num));
        if(n == 0)
        {
            len = 1;
        }else
        {
            if(n < 0)
            {
                sign = 1;
                n = -n;
            }
            while(n != 0)
            {
                num[len++] = n % 10;
                n /= 10;
            }
        }

    }

    friend ostream& operator << (ostream& os,bign n)
    {
        if(n.sign)
            os << '-';
        for(int i = n.len - 1;i >= 0;i--)
            os << n.num[i];
        return os;
    }
};

 大数计算

比较

在设计这些运算之前，我先搞定大数比较的问题，其实是想在大数减法上偷偷懒神马的。

//大数比较
    bool operator < (const Bigint & b) const
    {
        if(sign == b.sign)
        {
            if((!sign && !b.sign)&&len != b.len) return len < b.len;
            if((sign && b.sign)&&len != b.len) return len > b.len;
            if(sign)
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] > b.num[i];
            }else
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] < b.num[i];
            }
        }else
        {
            if(!sign && b.sign) return false;
            if(sign && !b.sign) return true;
        }
        return false;
    }

只需要写出一个小余，其他的操作都可以用小余来进行判断。

    bool operator > (const Bigint & b) const{return b < *this;}
    bool operator <= (const Bigint & b) const{return !(b < *this);}
    bool operator >= (const Bigint & b) const{return !(*this < b);}
    bool operator != (const Bigint & b) const{return b < *this || *this < b;}
    bool operator == (const Bigint & b) const{return !(b < *this) || !(*this < b);}

只为在减法的时候偷偷懒。

加法

在进行加法的时候进行了符号判断，虽然有点感觉是在画蛇添足，但是为了圆这个ADT式的谎，还是加上吧。

//加法
    bign operator + (const bign &b) const
    {
        bign c;
        //判断加后符号
        if(sign && b.sign)
            c.sign = 1;
        else if(!sign && b.sign)
            return c = b - *this;
        else if(sign && !b.sign)
            return c = *this - b;
        c.len = 0;
        for(int i = 0,g = 0;g || i < max(len,b.len);i++)
        {
            int x = g;
            if(i < len) x += num[i];
            if(i < b.len) x += b.num[i];
            c.num[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    bign operator += (const bign &b)
    {
        *this = *this + b;
        return *this;
    }

 减法

有了大数比较之后，就可以轻松的偷懒了。

//减法
    Bigint operator - (const Bigint &b) const
    {
        Bigint c;
        c.len = 0;
        if(*this > b)
        {
            c.sign = 0;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x += num[i];
                if(i < b.len) x -= b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else if(*this < b)
        {
            c.sign = 1;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x -= num[i];
                if(i < b.len) x += b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else
        {
            c = 0;
        }

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;

        return c;
    }
    Bigint operator -= (const Bigint &b)
    {
        *this = *this - b;
        return *this;
    }

 乘法

在写乘法之前特意去OJ找了两个加法和减法的题目，然后A掉，爽啊，想想还有最后一个乘法，常用大数类就搞出来了，那叫一个激动啊！！！

可以说乘法是比较难搞的，因为时间复杂度有点高。

//乘法
    Bigint operator * (const Bigint &b) const
    {
        Bigint c;
        if((sign && b.sign) || (!sign && !b.sign)) c.sign = 0;
        else c.sign = 1;

        //时间复杂度 O(len * b.len)
        for(int i = 0;i < len;i++)
            for(int j = 0;j < b.len;j++)
                c.num[c.len = max(i + j,c.len),i + j] += num[i] * b.num[j];

        for(int i = 0;i < c.len;i++)
        if(c.num[i] >= 10) {c.num[i + 1] += c.num[i] / 10;c.num[i] %= 10;}

        while(c.num[c.len] != 0)
            ++c.len;

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;
        return c;
    }
    Bigint operator *= (const Bigint &b)
    {
        *this = *this * b;
        return *this;
    }

到此，常用大数类算是完成了。（除了除法）

大数类代码

#include <iostream>
#include <cstring>

using namespace std;

#define MAX_LEN 1500  //存储大整数的整型数组的长度

class Bigint
{
private:
    bool sign;//是否非负数
    int len;  //长度
    int num[MAX_LEN];
public:
    Bigint(){len = 0;memset(num,0,sizeof(num));}
    Bigint(char *s)
    {
        sign = 0;
        int s_len = strlen(s);
        memset(num,0,sizeof(num));

        if(s[0] == '-')
        {
            sign = 1;
            int i = 0;
            len = s_len - 1;
            for(char *p = s + s_len - 1;p > s;p--)
                num[i++] = *p - '0';
        }else
        {
            int i = 0;
            len = s_len;
            for(char *p = s + s_len - 1;p >= s;p--)
                num[i++] = *p - '0';
        }

    }
    Bigint(int n)
    {
        len = 0;
        sign = 0;
        memset(num,0,sizeof(num));
        if(n == 0)//特判
        {
            len = 1;
        }else
        {
            if(n < 0){sign = 1;n = -n;}
            while(n != 0){num[len++] = n % 10;n /= 10;}
        }

    }
    //打印大数
    friend ostream& operator << (ostream& os,Bigint &n)
    {
        if(n.sign)//判断符号
            os << '-';
        while(n.num[n.len - 1] == 0)
            n.len--;
        for(int i = n.len - 1;i >= 0;i--)
            os << n.num[i];
        return os;
    }
    //大数比较
    bool operator < (const Bigint & b) const
    {
        if(sign == b.sign)
        {
            if((!sign && !b.sign)&&len != b.len) return len < b.len;
            if((sign && b.sign)&&len != b.len) return len > b.len;
            if(sign)
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] > b.num[i];
            }else
            {
                for(int i = len - 1;i >= 0;i--)
                    if(num[i] != b.num[i]) return num[i] < b.num[i];
            }
        }else
        {
            if(!sign && b.sign) return false;
            if(sign && !b.sign) return true;
        }
        return false;
    }
    bool operator > (const Bigint & b) const{return b < *this;}
    bool operator <= (const Bigint & b) const{return !(b < *this);}
    bool operator >= (const Bigint & b) const{return !(*this < b);}
    bool operator != (const Bigint & b) const{return b < *this || *this < b;}
    bool operator == (const Bigint & b) const{return !(b < *this) || !(*this < b);}
    //加法
    Bigint operator + (const Bigint &b) const
    {
        Bigint c;
        //判断加后符号
        if(sign && b.sign)
            c.sign = 1;
        else if(!sign && b.sign)
            return c = *this - b;
        else if(sign && !b.sign)
            return c = b - *this;
        c.len = 0;
        for(int i = 0,g = 0;g || i < max(len,b.len);i++)
        {
            int x = g;
            if(i < len) x += num[i];
            if(i < b.len) x += b.num[i];
            c.num[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    Bigint operator += (const Bigint &b)
    {
        *this = *this + b;
        return *this;
    }
    //减法
    Bigint operator - (const Bigint &b) const
    {
        Bigint c;
        c.len = 0;
        if(*this > b)
        {
            c.sign = 0;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x += num[i];
                if(i < b.len) x -= b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else if(*this < b)
        {
            c.sign = 1;
            for(int i = 0;i < max(len,b.len);i++)
            {
                int x = 0;
                if(i < len) x -= num[i];
                if(i < b.len) x += b.num[i];
                if(c.len > 0 && c.num[c.len - 1] < 0){c.num[c.len - 1] += 10;x--;}
                c.num[c.len++] = x;
            }
        }else
        {
            c = 0;
        }

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;

        return c;
    }
    Bigint operator -= (const Bigint &b)
    {
        *this = *this - b;
        return *this;
    }
    //乘法
    Bigint operator * (const Bigint &b) const
    {
        Bigint c;
        if((sign && b.sign) || (!sign && !b.sign)) c.sign = 0;
        else c.sign = 1;

        //时间复杂度 O(len * b.len)
        for(int i = 0;i < len;i++)
            for(int j = 0;j < b.len;j++)
                c.num[c.len = max(i + j,c.len),i + j] += num[i] * b.num[j];

        for(int i = 0;i < c.len;i++)
        if(c.num[i] >= 10) {c.num[i + 1] += c.num[i] / 10;c.num[i] %= 10;}

        while(c.num[c.len] != 0)
            ++c.len;

        while(c.num[c.len - 1] == 0 && c.len > 0)
            c.len--;
        if(c.len == 0) c.len = 1;
        return c;
    }
    Bigint operator *= (const Bigint &b)
    {
        *this = *this * b;
        return *this;
    }
    //除法
    Bigint operator / (const long long b) const
    {
        Bigint c;
        c.sign = 0;
        long long n[MAX_LEN];
        long long n_len = 0;
        long long yushu = 0;

        int tf = 0;
        for(int i = len;i >= 0;i--)
        {
            if((yushu * 10 + num[i]) / b)
            {
                tf = 1;
                n[n_len++] = (yushu * 10 + num[i]) / b;
                yushu = (yushu * 10 + num[i]) % b;
            }else
            {
                if(tf)
                    n[n_len++] = 0;
                yushu = yushu * 10 + num[i];
            }
        }

        c.len = n_len;

        for(int i = 0;i < n_len;i++)
        {
            c.num[i] = n[n_len - 1 - i];
        }
        if(c.len == 0)
            c.len = 1;
        return c;
    }
    Bigint operator /= (const long long &b)
    {
        *this = *this / b;
        return *this;
    }
    //取余
    long long operator % (const long long b) const
    {
        long long yushu = 0;

        for(int i = len;i >= 0;i--)
        {
            if((yushu * 10 + num[i]) / b)
            {
                yushu = (yushu * 10 + num[i]) % b;
            }else
            {
                yushu = yushu * 10 + num[i];
            }
        }

        return yushu;
    }
    Bigint operator %= (const long long &b)
    {
        *this = *this % b;
        return *this;
    }
};