1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 using namespace std;
  5 const int M=400;
  6 const int BASE=10;
  7 //****************************************
  8 class BigInt
  9 {
 10     friend BigInt operator+(const BigInt &a,const BigInt &b);
 11     friend BigInt operator*(const BigInt &a,const BigInt &b);
 12     friend BigInt operator-(const BigInt &a,const BigInt &b);
 13     friend BigInt operator/(const BigInt &a,const BigInt &b);
 14     friend ostream& operator<<( ostream &os,BigInt &a);
 15     //friend power(BigInt &BASE,BigInt &n);
 16 private:
 17     static int pos;    
 18     //小數(shù)點的位置 pos存放小數(shù)點后第一位。比如：3456.123 pos存放6
 19     int sign;   //數(shù)的正負(fù) 1為正數(shù)，-1為負(fù)數(shù)，
 20     int before; // 小數(shù)點前的位數(shù)
 21     int after;  //小數(shù)點后的位數(shù)
 22     int data[M];
 23 //    BigInt NormalAdd(const BigInt &a,const BigInt &b);
 24     BigInt NormalAdd(const BigInt &a);// 不考慮符號加法運算 return this+a
 25     BigInt NormalSubtract( const BigInt & a); //要求this>a進(jìn)行減法 ,且不考慮符號
 26 public:
 27     BigInt();
 28     BigInt( string str);
 29     static void SetPos(int m){pos=m;}
 30     int AbsCompare(const BigInt &a);
 31     int Compare(const BigInt &a); // this>a return 1 ;this<a return -1;this ==a reuturn 0;
 32     BigInt Add( BigInt &a);
 33     BigInt Subtract(BigInt &a);
 34     BigInt Mul(const BigInt &a);
 35 };
 36 //****************************************
 37 BigInt::BigInt()
 38 {
 39     memset(data,0,sizeof(data));
 40     after=0;
 41     sign=1;
 42     before=0;
 43 }
 44 //***********************************************************
 45 BigInt::BigInt( string str)
 46 {
 47     memset(data,0,sizeof(data));
 48     if(str[0]!='-')
 49         sign=1;
 50     else sign=-1;
 51     if(str[0]=='-' || str[0]=='+')
 52         str.erase(0,1);
 53     unsigned int loc=str.find('.',0);
 54     int len=str.length();
 55     if(loc==string::npos)
 56     {
 57         after=0;
 58         before=len;
 59         for(int i=len-1,j=pos;i>=0;--i,++j)
 60         {
 61             data[j]=str[i]-'0';
 62         }
 63     }
 64     else
 65     {
 66         for(int i=loc-1,j=pos;i>=0;--i,++j)
 67         {
 68             data[j]=str[i]-'0';
 69         }
 70         before=loc;
 71         for(int i=loc+1,j=pos-1;i<len;++i,--j)
 72         {
 73             data[j]=str[i]-'0';
 74         }
 75         after=len-loc-1;
 76     }
 77     while(after>0 && data[pos-after]==0)
 78         --after;
 79 
 80     while(before>0 && data[pos+before-1]==0)
 81         --before;
 82 }
 83 //***********************************************************
 84 //*********************************************************************
 85 BigInt BigInt::NormalAdd(const BigInt & a)
 86 {
 87     BigInt res;
 88     res.sign=sign;
 89     res.after=a.after>after ? a.after:after;
 90     int bef=a.before>before ? a.before: before;
 91     for(int i=pos-res.after; i<pos+bef; ++i)
 92     {
 93         res.data[i]+=data[i]+a.data[i];
 94         if(res.data[i]>=BASE)
 95         {
 96             res.data[i+1]+=res.data[i]/BASE;
 97             res.data[i]%=BASE;
 98         }
 99     }
100     while(res.data[pos+bef])
101     {
102         res.data[pos+bef+1]+=res.data[pos+bef]/BASE;
103         res.data[pos+bef]%=BASE;
104         ++bef;
105     }
106     res.before=bef;
107     while(res.after>0 && res.data[pos-res.after]==0)
108     {
109         --res.after;
110     }
111     return res;
112 }
113 //********************************************************
114 int BigInt::AbsCompare(const BigInt &a)
115 {
116     if(before>a.before) return 1;
117     else if(before<a.before) return -1;
118     else 
119     {
120         int t=after>a.after ? after: a.after;
121         t=pos-t;
122         for(int i=pos+before-1; i>=t; --i)
123         {
124             if(data[i]>a.data[i])
125                 return 1;
126             else if(data[i]<a.data[i])
127                 return -1;
128         }
129     }
130     return 0;
131 }
132 //*********************************************************
133 int BigInt::Compare(const BigInt &a)
134 {
135     if(sign>a.sign) return 1;
136     else if(sign<a.sign) return -1;
137     else return sign*AbsCompare(a);
138 }
139 //**********************************************************
140 BigInt BigInt::NormalSubtract( const BigInt  &a)
141 {
142     BigInt res;
143     res.after=after>a.after ? after: a.after;
144     for(int i=pos-res.after; i<pos+before; ++i)
145     {
146         res.data[i]=data[i]-a.data[i];
147     }
148     for(int i=pos-res.after; i<pos+before; ++i)
149     {
150         if(res.data[i]<0)
151         {
152             res.data[i]+=BASE;
153             res.data[i+1]-=1;
154         }
155     }
156     int bef=before;
157     while(bef)
158     {
159         if(res.data[pos+bef-1])
160             break;
161         --bef;
162     }
163     res.before=bef;
164     while(res.after>0 && res.data[pos-res.after]==0)
165     {
166         --res.after;
167     }
168     return res;
169 }
170 //*********************************************************
171 BigInt BigInt::Add( BigInt &a)
172 {
173     if(sign==a.sign)
174         return NormalAdd(a);
175     BigInt res;
176     if(sign>a.sign)
177     {
178         if(AbsCompare(a)>=0)  
179         {
180             res=NormalSubtract(a);
181             res.sign=1;
182         }
183         else
184         {
185             res=a.NormalSubtract(*this);
186             res.sign=-1;
187         }
188     }
189     else if(sign<a.sign)
190     {
191         if(AbsCompare(a)>0)
192         {
193             res=NormalSubtract(a);
194             res.sign=-1;
195         }
196         else 
197         {
198             res=a.NormalSubtract(*this);
199             res.sign=1;
200         }
201     }
202     return res;
203 }
204 //********************************************************
205 BigInt BigInt::Subtract(BigInt &a)
206 {
207     if(sign!=a.sign)
208     {
209         return NormalAdd(a);
210     }
211     BigInt res;
212     if(sign==1)
213     {
214         if(AbsCompare(a)>=0)
215         {
216             res=NormalSubtract(a);
217             res.sign=1;
218         }
219         else 
220         {
221             res=a.NormalSubtract(*this);
222             res.sign=-1;
223         }
224     }
225     else if(sign==-1)
226     {
227         if(AbsCompare(a)>0)
228         {
229             res=NormalSubtract(a);
230             res.sign=-1;
231         }
232         else
233         {
234             res=a.NormalSubtract(*this);
235             res.sign=1;
236         }
237     }
238     return res;
239 }
240 //********************************************************
241 BigInt BigInt::Mul(const BigInt &a)
242 {
243     BigInt res;
244     if(sign!=a.sign)  res.sign=-1;
245     else res.sign=1;
246     int len=before+after;
247     int alen=a.before+a.after;
248     for(int i=0,j=pos-after; i<len; ++i,++j)   //計算
249     {
250         for(int k=0,t=a.pos-a.after; k<alen; ++k,++t)
251         {
252             res.data[i+k]+=data[j]*a.data[t];
253         }
254     }
255     for(int i=0;i<len+alen;++i)  //進(jìn)位
256     {
257         if(res.data[i]>=BASE)
258         {
259             res.data[i+1]+=res.data[i]/BASE;
260             res.data[i]%=BASE;
261         }
262     }
263     int shift=pos-after-a.after;                //計算應(yīng)該移動的位數(shù)
264     for(int i=len+alen; i>=0; --i)
265     {
266         res.data[i+shift]=res.data[i];
267         res.data[i]=0;
268     }
269     int i=0;
270     while(i<pos)
271     {
272         if(res.data[i]>0) break;
273         ++i;
274     }
275     res.after=pos-i;
276     int bef=alen+len+shift;
277     if(res.data[bef]>0)
278     {
279         while(res.data[bef])
280         {
281             res.data[bef+1]=res.data[bef]/BASE;
282             res.data[bef]%=BASE;
283             ++bef;
284         }
285         res.before=bef-pos;
286     }
287     else 
288     {
289         while(bef>=pos)
290         {
291             if(res.data[bef]>0) break;
292             --bef;
293         }
294         res.before=bef-pos+1;
295     }
296     return res;
297 }
298 //********************************************************
299 ostream & operator<<(ostream &os,BigInt &a)
300 {
301     if(a.sign==-1)
302         os<<'-';
303     for(int i=a.before+a.pos-1; i>=a.pos; --i)
304         os<<a.data[i];
305     if(a.after>0)
306     {
307         os<<'.';
308         for(int i=a.pos-1; i>=a.pos-a.after; --i)
309             os<<a.data[i];
310     }
311     if(a.after==0 && a.before==0)
312         os<<'0';
313     return os;
314 }
315 //********************************************************
316 int BigInt::pos=200;
317