1 #include <iostream>  2 #include <string>  3 #include <iomanip>  4 #include <algorithm>  5 #include <cstring>  6 using namespace std;  7 #define MAXN 9999 // 大数类里面的数组中每个单元的最大正整数  8 #define MAXSIZE 10  9 #define DLEN 4 // 对应于MAXN的大小 10 #define MAX_LEN 500 11 class BigNum{ 12 public: 13     int a[MAX_LEN];    //可以控制大数的位数 14     int len;       //大数长度 15 public: 16     BigNum(){len = 1; memset(a,0,sizeof(a));} //构造函数 17     BigNum(const int);   //将一个int类型的变量转化为大数 18     BigNum(const char*); //将一个字符串类型的变量转化为大数 19     BigNum(const BigNum&);  //拷贝构造函数 20     BigNum &operator =(const BigNum&);//重载赋值运算符，大数之间进行赋值运算 21  22     friend istream& operator >>(istream&,BigNum&);//重载输入运算符 23     friend ostream& operator <<(ostream&,BigNum&);//重载输出运算符 24  25     BigNum operator +(const BigNum&) const;//重载加法运算符，两个大数之间的相加运算 26     BigNum operator -(const BigNum&) const;//重载减法运算符，两个大数之间的相减运算 27     BigNum operator *(const BigNum&) const;//重载乘法运算符，两个大数之间的相乘运算 28     BigNum operator /(const int&) const;//重载除法运算符，大数对一个整数进行相除运算 29  30     BigNum operator ^(const int&) const;//大数的n次方运算 31     int    operator %(const int&) const;//大数对一个int类型的变量进行取模运算 32     bool   operator >(const BigNum& T)const;//大数和另一个大数的大小比较 33     bool   operator >(const int& t)const; //大数和一个int类型的变量的大小比较 34  35     void print(); //输出大数 36 }; 37 BigNum::BigNum(const int b){//将一个int类型的变量转化为大数 38     int c,d = b; 39     len = 0; 40     memset(a,0,sizeof(a)); 41     while(d > MAXN){ 42         c = d - (d / (MAXN + 1)) * (MAXN + 1); 43         d = d / (MAXN + 1); 44         a[len++] = c; 45     } 46     a[len++] = d; 47 } 48 BigNum::BigNum(const char*s){//将一个字符串类型的变量转化为大数 49     int t,k,index,l,i; 50     memset(a,0,sizeof(a)); 51     l = strlen(s); 52     len = l / DLEN; 53     if(l % DLEN) len++; 54     index = 0; 55     for(i = l - 1 ; i >= 0 ; i -= DLEN){ 56         t = 0; 57         k = i - DLEN + 1; 58         if(k < 0) k = 0; 59         for(int j = k ; j <= i ; j++) 60             t = t * 10 + s[j] - ‘0‘; 61         a[index++] = t; 62     } 63 } 64 BigNum::BigNum(const BigNum& T) : len(T.len){//拷贝构造函数 65     int i; 66     memset(a,0,sizeof(a)); 67     for(i = 0 ; i < len ; i++) 68         a[i] = T.a[i]; 69 } 70 BigNum& BigNum::operator =(const BigNum& n){//重载赋值运算符，大数之间进行赋值运算 71     int i; 72     len = n.len; 73     memset(a,0,sizeof(a)); 74     for(i = 0 ; i < len ; i++) 75         a[i] = n.a[i]; 76     return *this; 77 } 78 istream& operator >>(istream& in,BigNum& b){//重载输入运算符 79     char ch[MAXSIZE * 4]; 80     int i = -1; 81     in >> ch; 82     int l = strlen(ch); 83     int cnt = 0,sum = 0; 84     for(i = l - 1 ; i >= 0 ; ){ 85         sum = 0; 86         int t = 1; 87         for(int j = 0 ; j < 4 && i >= 0 ; j++,i--,t *= 10) 88             sum += (ch[i] - ‘0‘) * t; 89         b.a[cnt] = sum; 90         cnt++; 91     } 92     b.len = cnt++; 93     return in; 94 } 95 ostream& operator <<(ostream& out,BigNum& b){//重载输出运算符 96     int i; 97     cout << b.a[b.len - 1]; 98     for(i = b.len - 2 ; i >= 0 ; i--){ 99         cout.width(DLEN);100         cout.fill(‘0‘);101         cout << b.a[i];102     }103     return out;104 }105 BigNum BigNum::operator +(const BigNum& T) const{//两个大数之间的相加运算106     BigNum t(*this);107     int i,big;      //位数108     big = T.len > len ? T.len : len;109     for(i = 0 ; i < big ; i++){110         t.a[i] += T.a[i];111         if(t.a[i] > MAXN){112             t.a[i + 1]++;113             t.a[i] -= MAXN+1;114         }115     }116     if(t.a[big] != 0) t.len = big + 1;117     else t.len = big;118     return t;119 }120 BigNum BigNum::operator -(const BigNum& T) const{  //两个大数之间的相减运算121     int i,j,big;122     bool flag;123     BigNum t1,t2;124     if(*this > T){125         t1 = *this;126         t2 = T;127         flag = 0;128     }129     else{130         t1 = T;131         t2 = *this;132         flag = 1;133     }134     big = t1.len;135     for(i = 0 ; i < big ; i++)136         if(t1.a[i] < t2.a[i]){137             j = i + 1;138             while(t1.a[j] == 0) j++;139             t1.a[j--]--;140             while(j > i) t1.a[j--] += MAXN;141             t1.a[i] += MAXN + 1 - t2.a[i];142         }143         else t1.a[i] -= t2.a[i];144     t1.len = big;145     while(t1.a[len - 1] == 0 && t1.len > 1){146         t1.len--;147         big--;148     }149     if(flag) t1.a[big - 1] = 0 - t1.a[big - 1];150     return t1;151 }152 BigNum BigNum::operator *(const BigNum& T) const{//两个大数之间的相乘运算153     BigNum ret;154     int i,j,up;155     int temp,temp1;156     for(i = 0 ; i < len ; i++){157         up = 0;158         for(j = 0 ; j < T.len ; j++){159             temp = a[i] * T.a[j] + ret.a[i + j] + up;160             if(temp > MAXN){161                 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);162                 up = temp / (MAXN + 1);163                 ret.a[i + j] = temp1;164             }165             else{166                 up = 0;167                 ret.a[i + j] = temp;168             }169         }170         if(up != 0) ret.a[i + j] = up;171     }172     ret.len = i + j;173     while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;174     return ret;175 }176 BigNum BigNum::operator /(const int& b) const{//大数对一个整数进行相除运算177     BigNum ret;178     int i,down = 0;179     for(i = len - 1 ; i >= 0 ; i--){180         ret.a[i] = (a[i] + down * (MAXN + 1)) / b;181         down = a[i] + down * (MAXN + 1) - ret.a[i] * b;182     }183     ret.len = len;184     while(ret.a[ret.len - 1] == 0 && ret.len > 1)185         ret.len--;186     return ret;187 }188 int BigNum::operator %(const int& b) const{//大数对一个int类型的变量进行取模运算189     int i,d = 0;190     for (i = len - 1 ; i >= 0 ; i--)191         d = ((d * (MAXN + 1)) % b + a[i]) % b;192     return d;193 }194 BigNum BigNum::operator ^(const int& n) const{    //大数的n次方运算195     BigNum t,ret(1);196     int i;197     if(n < 0) exit(-1);198     if(n == 0) return 1;199     if(n == 1) return *this;200     int m = n;201     while(m > 1){202         t = *this;203         for(i = 1 ; i << 1 <= m ; i <<= 1) t = t * t;204         m -= i;205         ret = ret * t;206         if(m == 1) ret = ret * (*this);207     }208     return ret;209 }210 bool BigNum::operator >(const BigNum& T) const{   //大数和另一个大数的大小比较211     int ln;212     if(len > T.len) return true;213     else if(len == T.len){214         ln = len - 1;215         while(a[ln] == T.a[ln] && ln >= 0) ln--;216         if(ln >= 0 && a[ln] > T.a[ln]) return true;217         else return false;218     }219     else return false;220 }221 bool BigNum::operator >(const int& t) const{//大数和一个int类型的变量的大小比较222     BigNum b(t);223     return *this > b;224 }225 void BigNum::print(){    //输出大数226     int i;227     cout << a[len - 1];228     for(i = len - 2 ; i >= 0 ; i--){229         cout.width(DLEN);230         cout.fill(‘0‘);231         cout << a[i];232     }233     cout << endl;234 }235 int main(void){236     BigNum val;237     val = "123456789101112131415161718192021222324252627282930";238     val.print();239     val = "10"; BigNum val1 = "1234";240     BigNum val2 = "11";241     BigNum tmp = val + val1;242     tmp.print();243     tmp = val * val1;244     tmp.print();245     tmp = val1 / 10;246     tmp.print();247     tmp = val2 ^ 2;248     tmp.print();249     return 0;250 }