ACM大正整数运算模板

主要参考《算法竞赛入门经典》第五章。另外还参考了很多别人的博客，魔改的乱七八糟，因此对于除加法以外的四则运算的可靠性都不能保证。还有，用这个会很费时间，最好一般还是不要用，正常的题目应该都会有用long long肯定能解决的方法。

警告

再看一遍引言！

不能有负数。

可能有各种bug。

模板

#include<iostream>
#include<sstream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
struct big_int{
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;
    //赋值函数
    big_int(long long num = 0){
        *this = num;
    }
    //赋值运算符（long long）
    big_int operator = (long long num){
        s.clear();
        do{
            s.push_back(num%BASE);
            num /= BASE;
        }while(num > 0);
        return *this;
    }
    //赋值运算符（string)
    big_int operator = (const string& str){
        s.clear();
        int x, len = (str.length()-1) / WIDTH + 1;
        for(int i = 0 ; i < len ; i++){
            int end = str.length() - i*WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start, end-start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return *this;
    }
    //四则运算
    //+
    big_int operator + (const big_int& b) const{
        big_int c;
        c.s.clear();
        for(int i = 0, g = 0 ; ; i++){
            if(g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if(i < s.size()) x += s[i];
            if(i < b.s.size()) x += b.s[i];
            c.s.push_back(x%BASE);
            g = x / BASE;
        }
        return c;
    }
    big_int operator += (const big_int& b){
        *this = *this + b;
        return *this;
    }
    //-
    big_int operator - (const big_int& b){
        big_int c;
        c.s.clear();
        int MAX = max(s.size(),b.s.size());
        for(int i = 0 , g = 0 ; ; i++){
            if(g == 0 && i >= MAX)
                break;
            int x = g;
            if(i < s.size())
                x += s[i];
            if(i < b.s.size())
                x -= b.s[i];
            if(i == MAX-1)
                c.s.push_back(x%BASE);
            else
                c.s.push_back(abs(x%BASE));
            g=x / BASE;
        }
        while(c.s.back() == 0){
            c.s.erase(c.s.end()-1);
        }
        return c;
    }
    big_int operator -= (const big_int& b){
        *this = *this - b;
        return *this;
    }
    //*
    big_int operator * (const big_int& b){
        stringstream ss;
        for(int i = s.size()-1 ; i >= 0 ; i--)
            ss << s[i];
        string operand1 = ss.str();
        ss.str("");
        for(int i = b.s.size()-1 ; i >= 0 ; i--)
            ss << b.s[i];
        string operand2 = ss.str();
        vector<int> c, d, temp;
        for(int i = operand1.length()-1 ; i >= 0 ; i--)
            c.push_back(operand1[i]-'0');
        for(int i = operand2.length()-1 ; i >= 0 ; i--)
            d.push_back(operand2[i]-'0');

        int MAX = max(c.size(),d.size());
        for(int i = 0 ; i < MAX*2 + 1 ; i++)
            temp.push_back(0);
 
        for(int i = 0 ; i < c.size() ; i++)
            for(int j = 0 ; j < d.size() ; j++)
                temp[i+j] += c[i]*d[j];
        for(int i = 0 ; i < 2*MAX + 1 ; i++)
            if(temp[i] > 9){
                temp[i+1] += temp[i] / 10;
                temp[i] %= 10;
            }
        int m = 2 * MAX;
        while(temp[m] == 0)
            m--;
 
        big_int another;
        another.s.clear();
        int len = (m-1) / WIDTH+1;
 
        for(int i = 0 ; i < len ; i++)
            another.s.push_back(0);
        for(int i = 0 ; i < len ; i++){
            int x = 1;
            int k = 0;
            int end = min(m+1,(i+1) * WIDTH);
            int start = i * WIDTH;
            for(int j = start ; j < end ; j++){
                k += x * temp[j];
                x *= 10;
            }
            another.s[i] = k;
        }
        return another;
    }
    big_int operator *= (const big_int& b)
    {
        *this = *this * b;
        return *this;
    }
    ///
    big_int operator / (const big_int& b){
        string operand1,operand2,result;
        stringstream ss;
        for(int i = s.size()-1 ; i >= 0 ; i--)
            ss << s[i];
        operand1 = ss.str();
        ss.str("");
        for(int i = b.s.size() - 1 ; i >= 0 ; i--)
            ss << b.s[i];
        operand2 = ss.str();

        int len1, len2;
        len1 = operand1.length();
        len2 = operand2.length();
        if(len1 < len2)
            return 0;
        if(*this == b)
            return 1;
 
        vector<int> c,d;
        for(int i = 0 ; i < len1 ; i++){
            c.push_back(operand1[i]-'0');
            if(i < len2)
                d.push_back(operand2[i]-'0');
            else
                d.push_back(0);
        }
 
        int time = len1-len2;
        int len = len1;
        int k, l = 0;
        for(int i = 0 ; i <= time ; i++){
            int ok = 1;
            k = 0;
            do{
                if(c[l] == 0){
                    l++;
                    ok = 0;
                    len1--;
                }
                if(len == len1){
                    int j = 0;
                    while(j < len2){
                        if(c[i+j] > d[j]){
                            ok = 1;
                            break;
                        }
                        else if(c[i+j] < d[j]){
                            ok = 0;
                            break;
                        }
                        j++;
                    }
                }
                if(ok){
                    for(int j = 0 ; j < len ; j++){
                        c[j+i] -= d[j];
                        if(c[j+i] < 0){
                            c[j+i-1]--;
                            c[j+i] += 10;
                        }
                    }
                    k++;
                }
            }while(ok);
            len--;
            result += k+'0';
        }
        big_int temp;
        temp = result;
        return temp;
    }
    big_int operator /= (const big_int& b){
        *this = *this / b;
        return *this;
    }
    //%
    big_int operator % (const big_int& b){
        big_int c; 
        c = *this - (*this / b) * b;
        return c;
    }
    big_int operator %= (const big_int& b){
        *this = *this % b;
        return *this;
    }
    //比较
    bool operator < (const big_int& b) const{
        if(s.size() != b.s.size()) return s.size() < b.s.size();
        for(int i = s.size()-1 ; i >= 0 ; i--){
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const big_int& b) const{
        return b < *this;
    }
    bool operator <= (const big_int& b) const{
        return !(b < *this);
    }
    bool operator >= (const big_int& b) const{
        return !(*this < b);
    }
    bool operator != (const big_int& b) const{
        return b < *this || *this < b;
    }
    bool operator == (const big_int& b) const{
        return !(b < *this) && !(*this < b);
    }
    //big_int <<
    friend ostream& operator << (ostream &out, const big_int& x){
        out << x.s.back();
        for(int i = x.s.size() - 2 ; i >= 0 ; i--){
            char buf[20];
            sprintf(buf, "%08d", x.s[i]);
            for(int j = 0 ; j < strlen(buf) ; j++){
                out << buf[j];
            }
        }
        return out;
    }
    //big_int >>
    friend istream& operator >> (istream &in, big_int& x){
        string s;
        if(!(in >> s)){
            return in;
        }
        x = s;
        return in;
    }
};
//////////////演示//////////////
int main(){
    ios::sync_with_stdio(false);
    big_int a, b;
    a = "123456789012347";
    b = 987654321;
    cout << "a " << a << endl;
    cout << "b " << b << endl;
    cout << "a+b " << a + b << endl;
    cout << "a-b " << a - b << endl;
    cout << "a*b " << a * b << endl;
    cout << "a/b " << a / b << endl;
    cout << "a%b " << (a % b) << endl;
    cout << "a<b " << (a < b) << endl;
    cout << "a>b " << (a > b) << endl;
    cout << "a!=b " << (a != b) << endl;
    cout << "a==b " << (a == b) << endl;
    return 0;
}