1 #include<iostream>  2 #include<vector>  3 #include<cmath>  4 #include<string>  5 #include<iomanip>  6 #include<algorithm>  7 using namespace std;  8   9 #define MAXN 10000 10 #define DLEN 4 11  12 class BigNum 13 { 14 private: 15     vector<int> A; 16     bool FLAG; 17     char cmp(const BigNum &,bool)const; 18     void TRIM(){while(!A.empty()&&!A.back())A.pop_back();if(A.empty())FLAG=0;} 19 public: 20     BigNum(){FLAG=0;} 21     BigNum(long long); 22     void swap(BigNum &T){std::swap(FLAG,T.FLAG);A.swap(T.A);} 23     void operator=(const BigNum &T){FLAG=T.FLAG;A=T.A;} 24     void operator=(const string &); 25     friend istream& operator>>(istream &,BigNum &); 26     friend ostream& operator<<(ostream &,BigNum); 27     bool   operator>(const BigNum &T){return this->cmp(T,0)>0;} 28     bool   operator<(const BigNum &T){return this->cmp(T,0)<0;} 29     BigNum operator-()const{BigNum T=*this;T.FLAG=~FLAG;return T;} 30     BigNum abs()const{BigNum T=*this;T.FLAG=0;return T;} 31     BigNum operator+(const BigNum &) const; 32     BigNum operator-(const BigNum &) const; 33     BigNum operator*(const BigNum &) const; 34     BigNum operator/(const BigNum &)const; 35     void operator+=(const BigNum &v){*this=*this+v;} 36     void operator-=(const BigNum &v){*this=*this-v;} 37     void operator*=(const BigNum &v){*this=*this*v;} 38     void operator/=(const BigNum &v){*this=*this/v;} 39     BigNum operator+(const long long a) const{return *this+BigNum(a);} 40     BigNum operator-(const long long a) const{return *this-BigNum(a);} 41     BigNum operator*(const long long a) const{return *this*BigNum(a);} 42     BigNum operator/(const long long a) const{return *this/BigNum(a);} 43 }; 44  45 char BigNum::cmp(const BigNum &a,bool flag)const 46 { 47     if(flag==0) 48     { 49         if(FLAG<a.FLAG) return 1; 50         if(FLAG>a.FLAG) return -1; 51     } 52     char F=!FLAG||flag?1:-1; 53     if(A.size()>a.A.size()) return F; 54     if(A.size()<a.A.size()) return -F; 55     for(int i=max(A.size(),a.A.size())-1;i>=0;i--) 56     { 57         if(A[i]>a.A[i]) return F; 58         if(A[i]<a.A[i]) return -F; 59     } 60     return 0; 61 } 62  63 BigNum::BigNum(long long a) 64 { 65     FLAG=0; 66     if(a<0) FLAG=1,a=-a; 67     for(;a;a/=MAXN) 68         A.push_back(a-(a/MAXN)*MAXN); 69 } 70  71 void BigNum::operator=(const string &s) 72 { 73     int len=0,n=0,m=0; 74     if(s[0]==‘-‘) FLAG=1,len=1; 75     for(int i=s.size()-1;i>=len;i--) 76     { 77         if(m==DLEN) A.push_back(n),m=0,n=0; 78         n+=(s[i]-‘0‘)*pow(10,m); 79         m++; 80     } 81     if(n>0)A.push_back(n); 82 } 83  84 istream& operator>>(istream &in,BigNum &T) 85 { 86     string s; 87     in>>s; 88     T=s; 89     return in; 90 } 91  92 ostream& operator<<(ostream &out,BigNum T) 93 { 94     if(T.FLAG) out<<‘-‘; 95     out<<T.A[T.A.size()-1]; 96     for(int i=T.A.size()-2;i>=0;i--) 97     { 98         out.width(DLEN); 99         out.fill(‘0‘);    100         out<<T.A[i];101     }102     return out;103 }104 105 BigNum BigNum::operator+(const BigNum &T) const106 {107     if(FLAG==T.FLAG)108     {109         BigNum t(*this);110         int j=max(A.size(),T.A.size());111         for(int i=0,is=0;i<j||is;i++)112         {113             if(i==t.A.size()) t.A.push_back(0);114             t.A[i]+=is+(i<T.A.size()?T.A[i]:0);115             is=t.A[i]>=MAXN;116             if(is)t.A[i]-=MAXN;117         }118         return t;119     }else return *this-(-T);120 }121 122 BigNum BigNum::operator-(const BigNum &T) const123 {124     if(FLAG==T.FLAG)125     {126         if(~cmp(T,1))127         {128             BigNum t(*this);129             for(int i=0,is=0;i<T.A.size()||is;i++)130             {131                 t.A[i]-=is+(i<T.A.size()?T.A[i]:0);132                 is=t.A[i]<0;133                 if(is) t.A[i]+=MAXN;134             }135             t.TRIM();136             return t;137         }else return -(T-*this);138     }else return *this+(-T);139 }140 141 BigNum BigNum::operator*(const BigNum &T) const142 {143     BigNum t;144     t.A.resize(A.size()+T.A.size());145     for(int i=0;i<A.size();i++)146         for(int j=0;j<T.A.size();j++)147         {148             t.A[i+j]+=A[i]*T.A[j];149             if(t.A[i+j]>=MAXN)150             {151                 t.A[i+j+1]+=t.A[i+j]/MAXN;152                 t.A[i+j]-=(t.A[i+j]/MAXN)*MAXN;153             }154         }155     t.TRIM();156     t.FLAG=FLAG*T.FLAG;157     return t;158 }159 160 BigNum BigNum::operator/(const BigNum &T)const161 {162     switch(this->cmp(T,1))163     {164         case -1:165             return 0;166         case 0:167             return 1;168         case 1:169             BigNum a(*this),b,c,d;170             long long n=this->A.size()-T.A.size();171             for(int i=n;i>=0;i--)172             {173                 c=pow(10,i);174                 b=T*c;175                 while((a-b).FLAG==0)176                 {177                     a=a-b;178                     d+=c;179                 }180             }181             return d;182     }183     return -1;184 }