首页 > 代码库 > 高精度模板

高精度模板

/*
    大整数Bignum类 开始写于2016.06.29
    #----- Version 1.0.0
        支持有符号运算
            已实现+,-,*(位数较大(位数之和>800)时FFT,较小时模拟),
            abs(绝对值)

    代码供学习交流使用,版权没有,欢迎盗版。
                                    -- 作者:sxysxy

    #----- Version 1.0.1 更新于2016.07.02
        实现 /(二分法), sqrt(二分法), pow(快速幂),log(暴力,因为考虑到答案一般都比较小)
        lg(即log(10)), factorial(阶乘)
        添加printB函数便于调试
                                    -- sxysxy

    LICENSE:
        This file is under GPL.
        You can redistribute it and/or modify it under the terms of the 
    GNU General Public License as published by the Free Software Foundation,
    either version 3 of the License, or (at your option) any later version.
*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <cstring>
#include <string>
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

#define BIGNUM_DEBUG 2333

class Bignum
{
    void mknum(const char *s, int len = -1)
    {
        sign = 0;
        if(*s == -)
        {
            mknum(s+1);
            sign = 1;
            return;
        }
        int l;
        if(len == -1)
            l = strlen(s);
        else
            l = len;
        l = strlen(s);
        bits.clear();
        bits.resize(l);
        for(int i = l-1; i >= 0; i--)
            bits[l-i-1] = s[i] - 0;
        maintain();
    }
    void mknum(string &s)
    {
        mknum(s.c_str(), s.length());
    }
//    -------------
    void us_addto(Bignum &b)  // unsigned add to
    {
        int mlen = max(b.bits.size(), bits.size());
        int slen = bits.size();
        int olen = b.bits.size();
        bits.resize(mlen);
        for(int i = 0; i < mlen; i++)
        {
            int s = 0;
            if(i < slen)s += bits[i];
            if(i < olen)s += b.bits[i];
            bits[i] = s;
        }
        maintain();
    }
    class FFTer
    {
        class Complex
        {
        public:
            double real, image;
            Complex(double a = 0, double b = 0)
            {
                real = a;
                image = b;
            }
            Complex operator + (const Complex &o){return Complex(real+o.real, image+o.image);}
            Complex operator - (const Complex &o){return Complex(real-o.real, image-o.image);}
            Complex operator * (const Complex &o){return Complex(real*o.real-image*o.image, real*o.image+o.real*image);}
            Complex operator * (double k){return Complex(real*k, image*k);}
            Complex operator / (double k){return Complex(real/k, image/k);}
        };
        public:
        vector<Complex> a;  //系数向量
        int n;                //多项式次数上界
        FFTer(vector<int> &vec)
        {
            a.resize(vec.size());
            for(int i = 0; i < vec.size(); i++)
                a[i].real = vec[i];
            n = vec.size();
        }
        void transform()
        {
            int j = 0;
            int k;
            for(int i = 0; i < n; i++)
            {
                if(j > i)swap(a[i], a[j]);
                k = n;
                while(j & (k >>= 1))j &= ~k;
                j |= k;
            }
        }
        void FFT(bool IDFT = false)
        {
            const double Pi = IDFT?-acos(-1.0):acos(-1.0);
                            //IDFT与DFT选择方向相反(符号相反)
            transform();    //交换元素(翻转二进制位,具体看下面注释,再具体看算导
            for(int s = 1; s < n; s <<= 1)
            {    //算法导论上是fot s = 1 to lgn,考虑到精度问题改为上面那个...
                for(int t = 0; t < n; t += s<<1)
                {
                //合并[t, t+s-1]与 [t+s, t+2*s-1] (算导上以指数形式给出,注意到他的s....)
                //合并为[t, t+2*s-1] (看起来像是废话) (有示例图在算导上,画得很形象的)
                /*                一个更简单的示例图
                    (翻转过程)          翻转             合并
                    00    ->    00        0-|--|---------------------------
                                      |  |                    
                    01    ->    10        1-|--|---\ /---------------------
                                      |     |    X             
                    10    ->    01        2-|--|---/ \---------------------
                                      |  |          
                    11    ->    11        3-|--|---------------------------
                */
                    double x = Pi/s;
                    Complex omgn(cos(x), sin(x));
                    Complex omg(1.0, 0.0);    //单位向量
                    for(int m = 0; m < s; m++)
                    {            //旋转
                        int a1 = m+t;
                        int a2 = m+t+s;   //取两边系数向量的系数
                        //算导上管这个叫公共子表达式消除
                            //(其实就是一个变量计算一次然后保存下来用多次...嗯算导总是这么有逼格)
                        Complex comm = omg * a[a2];
                        a[a2] = a[a1] - comm;
                        a[a1] = a[a1] + comm;  //这两个顺序不要反了
                        omg = omg * omgn;
                    }
                }
            }
            if(IDFT)
                for(int i = 0; i < n; i++)
                    a[i] = a[i] / n;
        }
        void mul(FFTer &o)
        {
            int s = 1;
            while(s < n + o.n)s <<= 1;
            n = o.n = s;
            a.resize(s);
            o.a.resize(s);

            FFT(false);
            o.FFT(false);
            for(int i = 0; i < n; i++)
                a[i] = a[i] * o.a[i];
            FFT(true);
        }
    };
    void us_multo(Bignum &b)
    {
        FFTer x(bits);
        FFTer y(b.bits);
        x.mul(y);
        bits.clear();
        bits.resize(x.a.size());
        for(int i = 0; i < x.n; i++)
            bits[i] = (int)(x.a[i].real+0.5);
        maintain();
    }
    void us_multo_simu(Bignum &b)
    {
        vector<int> r;
        r.resize(max(length(),b.length())<<1);
        for(int i = 0; i < length(); i++)
            for(int j = 0; j < b.length(); j++)
                r[i+j] += bits[i] * b.bits[j];
        *(&(this -> bits)) = r;
        maintain();
    }
    void us_subto(Bignum &b) // abs(self) >= abs(other)
    {
        int mlen = length();
        int olen = b.length();
        for(int i = 0; i < mlen; i++)
        {
            int s = bits[i];
            if(i < olen)s -= b.bits[i];
            bits[i] = s;
            if(bits[i] < 0)
            {
                bits[i] += 10;
                bits[i+1] -= 1;
            }
        }
        for(int i = bits.size() - 1; !bits[i] && i >= 1; i--)bits.pop_back();
        if(bits.size() == 1 && bits[0] == 0)sign = 0;
    }
    void us_divto(Bignum &b)
    {
        if(length() == 1 && bits[0] == 0)return;
        Bignum L("0");
        L.sign = 0;
        Bignum R(*this);
        R.sign = 0;
        Bignum two("2");
        R *= two;
        Bignum one("1");
        one.sign = 0;
        while(L + one != R)
        {
            Bignum M = L+R;
            M.divto2();
            Bignum t = M*b;
            if(t > *this)
            {
                R = M;
            }else if(t < *this)
            {
                L = M;
            }else
            {
                *this = M;
                L = M;
                break;
            }
        }
        *this = L;
    }
public:
    int sign;
    vector<int> bits;
    int length()
    {
        return bits.size();
    }
    void maintain()
    {
        for(int i = 0; i < bits.size(); i++)
        {
            if(i + 1 < bits.size())
                bits[i+1] += bits[i]/10;
            else if(bits[i] > 9)
                bits.push_back(bits[i]/10);
            bits[i] %= 10;
        }
        if(bits.size() == 0)
        {
            bits.push_back(0);
            sign = 0;
        }
        for(int i = bits.size() - 1; !bits[i] && i >= 1; i--)bits.pop_back();
    }

    Bignum(string &s)
    {
        Bignum();
        mknum(s);
    }
    Bignum(const char *s)
    {
        Bignum();
        mknum(s);
    }
    Bignum(int n)
    {
        Bignum();
        char buf[15];
        sprintf(buf, "%d", n);
        mknum(buf);
    }
    Bignum()
    {
        sign = 0;
        bits.push_back(0);
    }
    Bignum(const Bignum& b) 
    {
        copy(b);
    }
    void copy(const Bignum& b)
    {
        sign = b.sign;
        bits = b.bits;
    }

// ------------------------------------------
    bool us_cmp(Bignum &b)   //无符号的比较
    {
        if(length() != b.length())return false;
        int l = length();
        for(int i = 0; i < l; i++)
            if(bits[i] != b.bits[i])
                return false;
        return true;
    }
    bool us_larger(Bignum &b)
    {
        if(length() > b.length())return true;
        else if(length() < b.length())return false;
        int l = length();
        for(int i = l-1; i >= 0; i--)
            if(bits[i] > b.bits[i])
                return true;
            else if(bits[i] < b.bits[i])
                return false;
        return false;
    }
    bool operator== (Bignum &o)
    {
        if(sign != o.sign)
            return false;
        return us_cmp(o);
    }
    bool operator!= (Bignum &o)
    {
        return !(*this == o);
    }
    bool operator> (Bignum &o)
    {
        if(sign == 0 && o.sign == 1)return true;
        if(sign == 1 && o.sign == 0)return false;
        if(sign == o.sign && sign)return !us_larger(o);
        return us_larger(o);
    }
    bool operator< (Bignum &o)
    {
        return !(*this == o || *this > o);   //小于就是不等于也不大于 
    }
    bool operator<= (Bignum &o)
    {
        return *this < o || *this == o;
    }
    bool operator>= (Bignum &o)
    {
        return *this > o || *this == o;
    }

// -------------------------------
    Bignum& operator+= (Bignum &o)
    {
        if(!sign && !o.sign)
        {
            us_addto(o);
            sign = 0;
        }
        else if(sign && o.sign)
        {
            us_addto(o);
            sign = 1;
        }
        else if(sign && !o.sign)
        {
            if(o.us_larger(*this))
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 0;
            }else
            {
                us_subto(o);
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }
        }else if(!sign && o.sign)
        {
            if(us_larger(o))
            {
                us_subto(o);
                sign = 0;
            }else
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }
        }
        return *this;
    }
    Bignum operator+ (Bignum &o)
    {
        Bignum t(*this);
        t += o;
        return t;
    }

// ------------------------------
    Bignum& operator*= (Bignum &o)
    {
        if(length() + o.length() > 800)
            us_multo(o);                 //FFT
        else
            us_multo_simu(o);             //simulate
        if(sign == o.sign)sign = 0;
        else sign = 1;
        return *this;
    }
    Bignum operator* (Bignum &o)
    {
        Bignum t(*this);
        t *= o;
        return t;
    }
// -------------------------------
    Bignum& operator-= (Bignum &o)
    {
        if(!sign && !o.sign) 
        {
            if(us_larger(o))
            {
                us_subto(o);
                sign = 0;
            }
            else
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }
        }else if(sign && o.sign)
        {
            if(us_larger(o))
            {
                us_subto(o);
                sign = 1;
                if(bits.size() == 1 && bits[0] == 0)sign = 0;
            }else
            {
                Bignum t(o);
                t.us_subto(*this);
                *this = t;
                sign = 0;
            }
        }else if(!sign && o.sign)
        {
            us_addto(o);
            sign = 0;
        }else if(sign && !o.sign)
        {
            us_addto(o);
            sign = 1;
        }
        return *this;
    }
    Bignum operator- (Bignum &o)
    {
        Bignum t(*this);
        t -= o;
        return t;
    }
// ---------------------------------
    Bignum& divto2()
    {
        if(!bits.size())return *this;
        bits[0] >>= 1;
        int i;
        for(i = 1; i < bits.size(); i++)
        {
            if(bits[i] & 1)bits[i-1] += 5;
            bits[i] >>= 1;
        }
        if(bits[i-1] == 0)bits.pop_back();
        return *this;
    }
    Bignum& operator/= (Bignum &o)
    {
        us_divto(o);
        if(sign == o.sign)sign = 0;
        else sign = 1;
        return *this;
    }
    Bignum operator/ (Bignum &o)
    {
        Bignum t(*this);
        t /= o;
        return t;
    }
// ---------------------------------
    Bignum abs()
    {
        Bignum t(*this);
        t.sign = 0;
        return t;
    }


    Bignum sqrt()
    {
        Bignum L("0"), R(*this);
        Bignum one("1");
        Bignum m, t;
        while(L + one != R)
        {
            m = L+R;
            m.divto2();
            Bignum t = m*m;
            if(t == *this)return m;
            else if(t > *this)R = m;
            else L = m;
        }
        return L;
    }

    //若e <= 0则会返回1
    //底数(也就是this)是负数的话会根据次数决定符号
    Bignum pow(Bignum &e)
    {
        if(e.sign)return 1;
        Bignum ans("1");
        Bignum base(*this);
        Bignum zero("0");
        Bignum exp(e);
        while(exp > zero)
        {
            if(exp.bits[0] & 1)
            {
                ans *= base;
            }
            base *= base;
            exp.divto2();
        }
        if(sign && e.bits[0] & 1)ans.sign = 1;
        return ans;
    }

    //注意,如果本数小于底数返回1...
    Bignum log(Bignum &base)
    {
        if(sign)return 0;
        if(length() == 1 && bits[0] == 1)return 0;
        if(*this <= base)return 1;
        Bignum one("1");

        Bignum r("1");
        Bignum c("0");
        while(r < *this)
        {
            r *= base;
            c += one;
        }
        if(r != *this)c -= one; 
        return c;
    }
    Bignum lg()
    {
        Bignum ten("10");
        return log(ten);
    }

    Bignum factorial()
    {
        Bignum r("1");
        Bignum zero("0");
        Bignum one("1");
        Bignum t(*this);
        while(t > zero)
        {
            r *= t;
            t -= one;
        }
        return r;
    }

// -----------------------------------    
    friend istream& operator>>(istream &is, Bignum &b)
    {
        string s;
        is >> s;
        b.mknum(s);
        return is;
    }
    friend ostream& operator<<(ostream &os, Bignum b)
    {
        if(b.sign)os << -;
        for(int i = b.bits.size()-1; i >= 0; i--)os << b.bits[i];
        return os;
    }

    string to_string()
    {
        int sz = length();
        string s;
        if(sign)
            s.resize(sz+1);
        else
            s.resize(sz);
        int i = 0;
        if(sign)s[i++] = -;
        for(int j = sz-1; i < sz+sign; i++, j--)
            s[i] = bits[j] + 0;
        return s;
    }    

};
    // --
#ifdef BIGNUM_DEBUG
    #ifdef __GNUC__ 
    __attribute__((noinline))     //禁止内联
    #endif
    #ifdef __MINGW32__
    __attribute__((noinline))
    #endif
    char* printB(Bignum &b)
    {
         //仅仅是用于能在gdb中使用它来输出自己 
        string s = b.to_string();
        char *buf = (char *)malloc(sizeof(char) * s.length());
                        //这个函数仅用于调试,这里申请的内存不会释放
                        //因此非调试时不要使用这个函数
        strcpy(buf, s.c_str());
        return buf;  //然后gdb中就可以 print printB(一个Bignum )
    }
#endif

int main()
{

    return 0;
}

 






2更简短的模板

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 410;

struct bign
{
    int len, s[MAXN];
    bign ()
    {
        memset(s, 0, sizeof(s));
        len = 1;
    }
    bign (int num) { *this = num; }
    bign (const char *num) { *this = num; }
    bign operator = (const int num)
    {
        char s[MAXN];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    bign operator = (const char *num)
    {
        for(int i = 0; num[i] == 0; num++) ;  //去前导0
        len = strlen(num);
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - 0;
        return *this;
    }
    bign operator + (const bign &b) const //+
    {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    bign operator += (const bign &b)
    {
        *this = *this + b;
        return *this;
    }
    void clean()
    {
        while(len > 1 && !s[len-1]) len--;
    }
    bign operator * (const bign &b) //*
    {
        bign c;
        c.len = len + b.len;
        for(int i = 0; i < len; i++)
        {
            for(int j = 0; j < b.len; j++)
            {
                c.s[i+j] += s[i] * b.s[j];
            }
        }
        for(int i = 0; i < c.len; i++)
        {
            c.s[i+1] += c.s[i]/10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    bign operator *= (const bign &b)
    {
        *this = *this * b;
        return *this;
    }
    bign operator - (const bign &b)
    {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; i < len; i++)
        {
            int x = s[i] - g;
            if(i < b.len) x -= b.s[i];
            if(x >= 0) g = 0;
            else
            {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    bign operator -= (const bign &b)
    {
        *this = *this - b;
        return *this;
    }
    bign operator / (const bign &b)
    {
        bign c, f = 0;
        for(int i = len-1; i >= 0; i--)
        {
            f = f*10;
            f.s[0] = s[i];
            while(f >= b)
            {
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;
        c.clean();
        return c;
    }
    bign operator /= (const bign &b)
    {
        *this  = *this / b;
        return *this;
    }
    bign operator % (const bign &b)
    {
        bign r = *this / b;
        r = *this - r*b;
        return r;
    }
    bign operator %= (const bign &b)
    {
        *this = *this % b;
        return *this;
    }
    bool operator < (const bign &b)
    {
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const bign &b)
    {
        if(len != b.len) return len > b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] > b.s[i];
        }
        return false;
    }
    bool operator == (const bign &b)
    {
        return !(*this > b) && !(*this < b);
    }
    bool operator != (const bign &b)
    {
        return !(*this == b);
    }
    bool operator <= (const bign &b)
    {
        return *this < b || *this == b;
    }
    bool operator >= (const bign &b)
    {
        return *this > b || *this == b;
    }
    string str() const
    {
        string res = "";
        for(int i = 0; i < len; i++) res = char(s[i]+0) + res;
        return res;
    }
};

istream& operator >> (istream &in, bign &x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream &out, const bign &x)
{
    out << x.str();
    return out;
}

int main()
{
    bign a, b, c, d, e, f, g;
    while(cin>>a>>b)
    {
        a.clean(), b.clean();
        c = a+b;
        d = a-b;
        e = a*b;
        f = a/b;
        g = a%b;
        cout<<"a+b"<<"="<<c<<endl; // a += b
        cout<<"a-b"<<"="<<d<<endl; // a -= b;
        cout<<"a*b"<<"="<<e<<endl; // a *= b;
        cout<<"a/b"<<"="<<f<<endl; // a /= b;
        cout<<"a%b"<<"="<<g<<endl; // a %= b;
        if(a != b) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

 3

#include<iostream> 
#include<string> 
#include<iomanip> 
#include<algorithm> 
using namespace std; 

#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4

class BigNum
{ 
private: 
    int a[500];    //可以控制大数的位数 
    int len;       //大数长度
public: 
    BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //构造函数
    BigNum(const int);       //将一个int类型的变量转化为大数
    BigNum(const char*);     //将一个字符串类型的变量转化为大数
    BigNum(const BigNum &);  //拷贝构造函数
    BigNum &operator=(const BigNum &);   //重载赋值运算符,大数之间进行赋值运算

    friend istream& operator>>(istream&,  BigNum&);   //重载输入运算符
    friend ostream& operator<<(ostream&,  BigNum&);   //重载输出运算符

    BigNum operator+(const BigNum &) const;   //重载加法运算符,两个大数之间的相加运算 
    BigNum operator-(const BigNum &) const;   //重载减法运算符,两个大数之间的相减运算 
    BigNum operator*(const BigNum &) const;   //重载乘法运算符,两个大数之间的相乘运算 
    BigNum operator/(const int   &) const;    //重载除法运算符,大数对一个整数进行相除运算

    BigNum operator^(const int  &) const;    //大数的n次方运算
    int    operator%(const int  &) const;    //大数对一个int类型的变量进行取模运算    
    bool   operator>(const BigNum & T)const;   //大数和另一个大数的大小比较
    bool   operator>(const int & t)const;      //大数和一个int类型的变量的大小比较

    void print();       //输出大数
}; 
BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
{ 
    int c,d = b;
    len = 0;
    memset(a,0,sizeof(a));
    while(d > MAXN)
    {
        c = d - (d / (MAXN + 1)) * (MAXN + 1); 
        d = d / (MAXN + 1);
        a[len++] = c;
    }
    a[len++] = d;
}
BigNum::BigNum(const char*s)     //将一个字符串类型的变量转化为大数
{
    int t,k,index,l,i;
    memset(a,0,sizeof(a));
    l=strlen(s);   
    len=l/DLEN;
    if(l%DLEN)
        len++;
    index=0;
    for(i=l-1;i>=0;i-=DLEN)
    {
        t=0;
        k=i-DLEN+1;
        if(k<0)
            k=0;
        for(int j=k;j<=i;j++)
            t=t*10+s[j]-0;
        a[index++]=t;
    }
}
BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数
{ 
    int i; 
    memset(a,0,sizeof(a)); 
    for(i = 0 ; i < len ; i++)
        a[i] = T.a[i]; 
} 
BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符,大数之间进行赋值运算
{
    int i;
    len = n.len;
    memset(a,0,sizeof(a)); 
    for(i = 0 ; i < len ; i++) 
        a[i] = n.a[i]; 
    return *this; 
}
istream& operator>>(istream & in,  BigNum & b)   //重载输入运算符
{
    char ch[MAXSIZE*4];
    int i = -1;
    in>>ch;
    int l=strlen(ch);
    int count=0,sum=0;
    for(i=l-1;i>=0;)
    {
        sum = 0;
        int t=1;
        for(int j=0;j<4&&i>=0;j++,i--,t*=10)
        {
            sum+=(ch[i]-0)*t;
        }
        b.a[count]=sum;
        count++;
    }
    b.len =count++;
    return in;

}
ostream& operator<<(ostream& out,  BigNum& b)   //重载输出运算符
{
    int i;  
    cout << b.a[b.len - 1]; 
    for(i = b.len - 2 ; i >= 0 ; i--)
    { 
        cout.width(DLEN); 
        cout.fill(0); 
        cout << b.a[i]; 
    } 
    return out;
}

BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
{
    BigNum t(*this);
    int i,big;      //位数   
    big = T.len > len ? T.len : len; 
    for(i = 0 ; i < big ; i++) 
    { 
        t.a[i] +=T.a[i]; 
        if(t.a[i] > MAXN) 
        { 
            t.a[i + 1]++; 
            t.a[i] -=MAXN+1; 
        } 
    } 
    if(t.a[big] != 0)
        t.len = big + 1; 
    else
        t.len = big;   
    return t;
}
BigNum BigNum::operator-(const BigNum & T) const   //两个大数之间的相减运算 
{  
    int i,j,big;
    bool flag;
    BigNum t1,t2;
    if(*this>T)
    {
        t1=*this;
        t2=T;
        flag=0;
    }
    else
    {
        t1=T;
        t2=*this;
        flag=1;
    }
    big=t1.len;
    for(i = 0 ; i < big ; i++)
    {
        if(t1.a[i] < t2.a[i])
        { 
            j = i + 1; 
            while(t1.a[j] == 0)
                j++; 
            t1.a[j--]--; 
            while(j > i)
                t1.a[j--] += MAXN;
            t1.a[i] += MAXN + 1 - t2.a[i]; 
        } 
        else
            t1.a[i] -= t2.a[i];
    }
    t1.len = big;
    while(t1.a[len - 1] == 0 && t1.len > 1)
    {
        t1.len--; 
        big--;
    }
    if(flag)
        t1.a[big-1]=0-t1.a[big-1];
    return t1; 
} 

BigNum BigNum::operator*(const BigNum & T) const   //两个大数之间的相乘运算 
{ 
    BigNum ret; 
    int i,j,up; 
    int temp,temp1;   
    for(i = 0 ; i < len ; i++)
    { 
        up = 0; 
        for(j = 0 ; j < T.len ; j++)
        { 
            temp = a[i] * T.a[j] + ret.a[i + j] + up; 
            if(temp > MAXN)
            { 
                temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); 
                up = temp / (MAXN + 1); 
                ret.a[i + j] = temp1; 
            } 
            else
            { 
                up = 0; 
                ret.a[i + j] = temp; 
            } 
        } 
        if(up != 0) 
            ret.a[i + j] = up; 
    } 
    ret.len = i + j; 
    while(ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--; 
    return ret; 
} 
BigNum BigNum::operator/(const int & b) const   //大数对一个整数进行相除运算
{ 
    BigNum ret; 
    int i,down = 0;   
    for(i = len - 1 ; i >= 0 ; i--)
    { 
        ret.a[i] = (a[i] + down * (MAXN + 1)) / b; 
        down = a[i] + down * (MAXN + 1) - ret.a[i] * b; 
    } 
    ret.len = len; 
    while(ret.a[ret.len - 1] == 0 && ret.len > 1)
        ret.len--; 
    return ret; 
}
int BigNum::operator %(const int & b) const    //大数对一个int类型的变量进行取模运算    
{
    int i,d=0;
    for (i = len-1; i>=0; i--)
    {
        d = ((d * (MAXN+1))% b + a[i])% b;  
    }
    return d;
}
BigNum BigNum::operator^(const int & n) const    //大数的n次方运算
{
    BigNum t,ret(1);
    int i;
    if(n<0)
        exit(-1);
    if(n==0)
        return 1;
    if(n==1)
        return *this;
    int m=n;
    while(m>1)
    {
        t=*this;
        for( i=1;i<<1<=m;i<<=1)
        {
            t=t*t;
        }
        m-=i;
        ret=ret*t;
        if(m==1)
            ret=ret*(*this);
    }
    return ret;
}
bool BigNum::operator>(const BigNum & T) const   //大数和另一个大数的大小比较
{ 
    int ln; 
    if(len > T.len)
        return true; 
    else if(len == T.len)
    { 
        ln = len - 1; 
        while(a[ln] == T.a[ln] && ln >= 0)
            ln--; 
        if(ln >= 0 && a[ln] > T.a[ln])
            return true; 
        else
            return false; 
    } 
    else
        return false; 
}
bool BigNum::operator >(const int & t) const    //大数和一个int类型的变量的大小比较
{
    BigNum b(t);
    return *this>b;
}

void BigNum::print()    //输出大数
{ 
    int i;   
    cout << a[len - 1]; 
    for(i = len - 2 ; i >= 0 ; i--)
    { 
        cout.width(DLEN); 
        cout.fill(0); 
        cout << a[i]; 
    } 
    cout << endl;
}
int main()
{
    int i,n;
    BigNum x[101];      //定义大数的对象数组
    x[0]=1;
    for(i=1;i<101;i++)
        x[i]=x[i-1]*(4*i-2)/(i+1);
    while(scanf("%d",&n)==1 && n!=-1)
    {
        x[n].print();
    }
}

 更多参见http://www.mamicode.com/info-detail-454902.html 

高精度模板