1 #include <iostream>  2 #include <cstdio>  3 #include <cstdlib>  4 #include <cstring>  5 #define UNIT 10  6   7 using namespace std;  8   9 struct Bignum 10 { 11     int val[105]; 12     int len; 13  14     Bignum () 15     { 16         memset (val, 0, sizeof(val)); 17         len = 1; 18     } 19  20     Bignum operator = (const int &a) 21     { 22         int t, p = a; 23         len = 0; 24         while (p >= UNIT) 25         { 26             t = p - (p/UNIT)*UNIT; 27             p = p / UNIT; 28             val[len++] = t; 29         } 30         val[len++] = p; 31         return *this; 32     } 33  34     Bignum operator + (const Bignum &a) const//大数加大数 35     { 36         Bignum x = a; 37         int L; 38         L = a.len > len ? a.len : len; 39         for (int i = 0; i < L; ++i) 40         { 41             x.val[i] += val[i]; 42             if (x.val[i] >= UNIT) 43             { 44                 x.val[i+1]++; 45                 x.val[i] -= UNIT; 46             } 47         } 48         if (x.val[L] != 0) 49             x.len = L+1; 50         else 51             x.len = L; 52         return x; 53     } 54  55     Bignum operator - (const Bignum &a) const 56     { 57         bool flag; 58         Bignum x1, x2; 59         if (*this > a) 60         { 61             x1 = *this; 62             x2 = a; 63             flag = 0; 64         } 65         else 66         { 67             x1 = a; 68             x2 = *this; 69             flag = 1; 70         } 71         int j, L = x1.len; 72         for (int i = 0; i < L; ++i) 73         { 74             if (x1.val[i] < x2.val[i]) 75             { 76                 j = i+1; 77                 while (x1.val[j] == 0) 78                     j++; 79                 x1.val[j--]--; 80                 while (j > i) 81                     x1.val[j--] += UNIT-1; 82                 x1.val[i] += UNIT-x2.val[i]; 83             } 84             else 85                 x1.val[i] -= x2.val[i]; 86         } 87         while (x1.val[x1.len-1] == 0 && x1.len > 1) 88             x1.len--; 89         if (flag) 90             x1.val[x1.len-1] = -x1.val[x1.len-1]; 91         return x1; 92     } 93  94     Bignum operator * (const Bignum &a) const//大数乘大数 95     { 96         Bignum x; 97         int i, j, up; 98         int x1, x2; 99         for (i = 0; i < len; i++)100         {101             up = 0;102             for (j = 0; j < a.len; j++)103             {104                 x1 = val[i]*a.val[j] + x.val[i+j] + up;105                 if (x1 >= UNIT)106                 {107                     x2 = x1 - x1/UNIT*UNIT;108                     up = x1 / UNIT;109                     x.val[i+j] = x2;110                 }111                 else112                 {113                     up = 0;114                     x.val[i+j] = x1;115                 }116             }117             if (up != 0)118                 x.val[i+j] = up;119         }120         x.len = i + j;121         while (x.val[x.len-1] == 0 && x.len > 1)122             x.len--;123         return x;124     }125 126     Bignum operator / (const int &a) const//大数除小数127     {128         Bignum x;129         int down = 0;130         for (int i = len-1; i >= 0; --i)131         {132             x.val[i] = (val[i]+down*UNIT) / a;133             down = val[i] + down*UNIT - x.val[i]*a;134         }135         x.len = len;136         while (x.val[x.len-1] == 0 && x.len > 1)137             x.len--;138         return x;139     }140 141     int operator % (const int &a) const//大数模小数142     {143         int x = 0;144         for (int i = len-1; i >= 0; --i)145             x = ((x*UNIT)%a+val[i]) % a;146         return x;147     }148 149     Bignum operator ^ (const int &a) const150     {151         Bignum p, x;152         x.val[0] = 1;153         if(a < 0)154             exit(-1);155         if(a == 0)156             return x;157         if(a == 1)158             return *this;159         int n = a, i;160         while(n > 1)161         {162             p = *this;163             for(i = 1; (i<<1) <= n; i<<=1)164                 p = p * p;165             n -= i;166             x = x * p;167             if(n == 1)168                 x = x * (*this);169         }170         return x;171     }172 173     bool operator > (const Bignum &a) const174     {175         int now;176         if (len > a.len)177             return true;178         else if (len == a.len)179         {180             now = len - 1;181             while (val[now] == a.val[now] && now >= 0)182                 now--;183             if(now >= 0 && val[now] > a.val[now])184                 return true;185             else186                 return false;187         }188         else189             return false;190     }191 };192 193 int main()194 {195     /*f[0] = 1;196     for(int i=1;i<=100;i++)197     f[i]=f[i-1]*(4*i-2)/(i+1);//卡特兰数递推式198     int n;199     while(scanf("%d",&n)==1)200     {201         if(n==-1)202             break;203         f[n].print();204     }*/205     return 0;206 }