[ C++ 快速高精度模板 ] [ BigN类 ] 大整数类高精度模板 BigInt FFT 快速傅里叶变换

【原创转载请注明】瞎写的，如果代码有错，或者各位大佬有什么意见建议，望不吝赐教
更新日志：
　　对于规模较小的整数乘法使用$$O(n^2)$$方法，提高速度
　　modify()和operator[]的bug修正
　　除法速度提升
　　修正了除法崩溃的问题
　　修正了除数为零崩溃的问题
  1 /**
  2   * BigN Beata v1.3.1
  3   * By: Nathaniel
  4   * 13th,Dec,2017
  5  **/
  6 
  7 //This file provides four operation for big-intgers
  8 //You can use class 'BigN' to define a variable.
  9 //Follow operators are available
 10 //+ - * / % = += -= *= /= %= > < >= <= == !=
 11 //these operators can used between BigN and BigN or BigN and int.
 12 
 13 //You can use function print() to print a BigN to stdout.
 14 //printn() will print a '
' at the end.
 15 //Function getstr() and str() will return a std::string-type string.
 16 
 17 //IN SAFE MODE, you can access k-th digit, from 0-th high digits, by [].
 18 //Or you can also modify x-th digit by modify(x,y).
 19 
 20 //In this template, multipy operator is implicated by fast_Fourier_transform,
 21 //Which can calculate convolution of to n-vectors in O(nlogn) time.
 22 //When number is small, this code still use O(n^2) algorithm.
 23 //and divide operator is implicated by dichotomy.
 24 
 25 //-O2 or -O3 optimize option is recomended.
 26 
 27 //**********************************************************************//
 28 //If you delete the follow definition,the calc speed will improve
 29 //but when number become huge, especially over 2000000 digits,
 30 //it may NOT work correctly.
 31 //So, to make sure that you answer is correct, do NOT delete this line.
 32 
 33     //#define SAFE_CALC_MODE
 34 
 35 //**********************************************************************//
 36 
 37 #include <iostream>
 38 #include <algorithm>
 39 #include <cmath>
 40 #include <cstring>
 41 #include <cstdio>
 42 #include <cstdlib>
 43 #include <ctime>
 44 #include <string>
 45 #include <vector>
 46 #include <complex>
 47 
 48 const double _pi=acos(-1);
 49 
 50 class _fast_Fourier_transform
 51 {
 52     typedef std::complex<double> Cmplx;
 53     typedef std::vector<Cmplx>    E;
 54     typedef std::vector<int> Vec;
 55     private:
 56     int _n,_m,_N;
 57     Vec R;
 58 
 59     //butterfly operation
 60     inline void    Expand(int temp)
 61     {
 62         int    L=0; for(_N=1;_N<=temp;_N<<=1,L++);
 63         R.resize(_N+1);
 64         for(int i=0;i<_N;++i) R[i]=R[i>>1]>>1|(i&1)<<(L-1);
 65         return ;
 66     }
 67 
 68     //Fast Fourier Transform
 69     void    FFT(E& A,int f)
 70     {
 71         for(int i=0;i<_N;++i) if(i<R[i]) swap(A[i],A[R[i]]);
 72         for(int i=1;i<_N;i<<=1)
 73         {
 74             Cmplx wn(cos(_pi/i),f*sin(_pi/i));
 75             for(int j=0;j<_N;j+=i<<1)
 76             {
 77                 Cmplx w(1,0);
 78                 for(int k=0;k<i;++k,w*=wn)
 79                 {
 80                     Cmplx x=A[j+k],y=w*A[i+j+k];
 81                     A[j+k]=x+y; A[i+j+k]=x-y;
 82                 }
 83             }
 84         } return ;
 85     }
 86 
 87     inline Vec Mul(E& A,E& B)
 88     {
 89         Expand(_n+_m); A.resize(_N+1); B.resize(_N+1);
 90         FFT(A,1); FFT(B,1);//DFT
 91         for(int i=0;i<=_N;++i) A[i]*=B[i];//MUL
 92         FFT(A,-1);//IDFT
 93         std::vector<int> vec;
 94         for(int i=0;i<_n+_m-1;++i)
 95             vec.push_back((int)(A[i].real()/_N+0.5));
 96                     //fix deviation
 97         return vec;
 98     }
 99         
100 
101 
102     public:
103     inline Vec multi(Vec& AA,Vec& BB)
104     {
105         E A,B;
106         _n=AA.size(); _m=BB.size();
107         //turn two vectors to complex
108         A.resize(_n); B.resize(_m);
109         for(int i=0;i<_n;++i) A[i]=AA[i];
110         for(int i=0;i<_m;++i) B[i]=BB[i];
111         return Mul(A,B);
112     }
113 };
114 
115 class    _normal_mul
116 {
117     //O(n^2) multiply
118     typedef std::vector<int> Vec;
119     private:
120     inline Vec mul(Vec& A,Vec& B)
121     {
122         Vec vec; int _n,_m;
123         _n=(int)A.size(),_m=(int)B.size();
124         vec.resize(_n+_m);
125         for(int i=0;i<_n;++i) for(int j=0;j<_m;++j)
126             vec[i+j]+=A[i]*B[j];
127         return vec;
128     }
129     public:
130     inline Vec multi(Vec& AA,Vec& BB) { return mul(AA,BB); }
131 };
132 
133 #ifndef SAFE_CALC_MODE
134 #define DIGITS 1000
135 #else
136 #define DIGITS 10
137 #endif
138 
139 class Divide_By_Zero_Error { };
140 
141 class _data_container_of_BigN
142 {
143     private:
144     bool sym;//0 positive,1 negetive
145     unsigned int length;//total length of the number
146     std::vector<int> vec;//vector of data
147     
148     public:
149     typedef _data_container_of_BigN _this_class;
150     inline void    _set_zero()
151         { sym=0; length=1; vec.clear(); vec.push_back(0); }
152     _data_container_of_BigN() { _set_zero();}
153     _data_container_of_BigN(int x)
154     {
155         //turn int to BigN
156         _set_zero();
157         if(x) vec.pop_back();
158         if(x<0) sym=true,x=-x;
159         while(x)
160         {
161             vec.push_back(x%DIGITS);
162             x/=DIGITS;
163         }
164         update_length();
165     }
166     _data_container_of_BigN(const char* str)
167     {
168         int    _n=strlen(str),data=0,base=1,t=0;
169         vec.clear(); if(str[0]=='-') sym=true,t=1;
170         for(int i=_n-1; i>=t; --i)
171         {
172             data=data+(str[i]-48)*base;
173 #ifndef SAFE_CALC_MODE
174             if((_n-i)%3==0)
175 #endif
176             {
177                 vec.push_back(data),data=0,base=1;
178                 continue;
179             }
180             base*=10;
181         }
182         vec.push_back(data);
183         update_length();
184     }
185 
186     inline _this_class operator=(const char* str)
187     {
188         //turn char* to BigN
189         int    _n=strlen(str),data=0,base=1,t=0;
190         vec.clear(); if(str[0]=='-') sym=true,t=1;
191         for(int i=_n-1; i>=t; --i)
192         {
193             data=data+(str[i]-48)*base;
194 #ifndef SAFE_CALC_MODE
195             if((_n-i)%3==0)
196 #endif
197             {
198                 vec.push_back(data),data=0,base=1;
199                 continue;
200             }
201             base*=10;
202         }
203         vec.push_back(data);
204         update_length();
205         return *this;
206     }
207 
208     inline _this_class operator =(int x)
209     {
210         //turn int to BigN
211         _set_zero();
212         if(x) vec.pop_back();
213         if(x<0) sym=true,x=-x;
214         while(x)
215         {
216             vec.push_back(x%DIGITS);
217             x/=DIGITS;
218         }
219         update_length();
220         return *this;
221     }
222 
223     inline _this_class operator -()
224     {
225         _this_class C=*this;
226         C.sym=!C.sym;
227         return C;
228     }
229 
230 
231     inline int&    operator[](int x) { return vec[x]; }
232 
233     inline bool    is_positive() { return !sym; }
234     inline bool    is_negetive() { return sym; }
235 
236     //Fix -0 to 0
237     inline void    fix_zero()
238     { if(sym && length==1 && vec[0]==0) sym=!sym; }
239 
240     //get k-th digit
241     inline int    getkth(const int x)
242     {
243         if(x>=(int)length) return -1;
244         return vec[length-x-1];
245     }
246     //Modify
247     inline bool    modify(const int x,const int y)
248     {
249         if(x>=(int)length) return false;
250         vec[length-x-1]=y; update_length(); return true;
251     }
252         
253 
254     inline _this_class operator+(_this_class& B)
255     {
256         if(!sym && !B.sym) return positive_add(B);
257         if(sym && B.sym) return -positive_add(B);
258         if(sym && !B.sym)
259         {
260             if(compare_abs(B)>0) return -positive_minus(B);
261             return B.positive_minus(*this);
262         }
263         if(compare_abs(B)>0) return positive_minus(B);
264         return -B.positive_minus(*this);
265     }
266 
267     inline _this_class operator-(_this_class& B)
268     {
269         if(!sym && !B.sym)
270         {
271             if(compare_abs(B)>0) return positive_minus(B);
272             return -B.positive_minus(*this);
273         }
274         if(sym && B.sym)
275         {
276             if(compare_abs(B)>0) return -positive_minus(B);
277             return B.positive_minus(*this);
278         }
279         if(!sym && B.sym) return positive_add(B);
280         return -B.positive_add(*this);
281     }
282 
283     inline _this_class operator*(_this_class& B)
284     {
285         return sym^B.sym?-positive_muliply(B):
286             positive_muliply(B);
287     }
288 
289     inline _this_class operator/(_this_class& B)
290     {
291         try
292         {
293             return sym^B.sym?-positive_divide(B):
294             positive_divide(B);
295         }catch(...)
296         {
297             std::cerr << std::endl;
298             std::cerr << "	Error: Division is 0." << std::endl;
299         }
300         return B;
301     }
302 
303     inline _this_class operator%(_this_class& B)
304     {
305         try
306         {
307             return sym^B.sym?-positive_mod(B):
308             positive_mod(B);
309         }catch(...)
310         {
311             std::cerr << std::endl;
312             std::cerr << "	Error: Division is 0." << std::endl;
313         }
314         return *this;
315     }
316 
317     inline _this_class operator+(int B){ _this_class t=B; return *this+t; }
318     inline _this_class operator-(int B){ _this_class t=B; return *this-t; }
319     inline _this_class operator*(int B){ _this_class t=B; return *this*t; }
320     inline _this_class operator/(int B){ _this_class t=B; return *this/t; }
321     inline _this_class operator%(int B){ _this_class t=B; return *this%t; }
322 
323     inline _this_class operator+=(_this_class& B) { return *this=*this+B; }
324     inline _this_class operator-=(_this_class& B) { return *this=*this-B; }
325     inline _this_class operator*=(_this_class& B) { return *this=*this*B; }
326     inline _this_class operator/=(_this_class& B) { return *this=*this/B; }
327     inline _this_class operator%=(_this_class& B) { return *this=*this%B; }
328     inline _this_class operator+=(int B) { return *this=*this+B; }
329     inline _this_class operator-=(int B) { return *this=*this-B; }
330     inline _this_class operator*=(int B) { return *this=*this*B; }
331     inline _this_class operator/=(int B) { return *this=*this/B; }
332     inline _this_class operator%=(int B) { return *this=*this%B; }
333 
334     //Print func will print the number to stdout in casual format
335     void    print()
336     {
337         if(is_negetive()) printf("-");
338 #ifdef SAFE_CALC_MODE
339         for(int i=vec.size()-1;i>=0;--i)
340             printf("%d",vec[i]);
341 #else
342         printf("%d",vec[vec.size()-1]);
343         for(int i=vec.size()-2;i>=0;--i)
344             printf("%03d",vec[i]);
345 #endif
346         return ;
347     }
348     //Print func will print the number to 'str' in casual format
349     void    print_to_str(std::string& str)
350     {
351         str="";
352         char tempstr[4];
353         if(is_negetive()) str="-";
354 #ifdef SAFE_CALC_MODE
355         for(int i=vec.size()-1;i>=0;--i)
356             sprintf(tempstr,"%d",vec[i]),
357                 str+=tempstr;
358 #else
359         sprintf(tempstr,"%d",vec[vec.size()-1]);
360         str+=tempstr;
361         for(int i=vec.size()-2;i>=0;--i)
362             sprintf(tempstr,"%03d",vec[i]),
363                 str+=tempstr;
364 #endif
365         return ;
366     }
367 
368     inline unsigned int size() { return vec.size(); }
369 
370     /*
371         *     this func
372         *     returns 1 if *this>B
373         *     returns -1 if *this<B
374         *     return 0 if *this==B
375     */
376     inline int    compare_abs(_this_class& B)
377     {
378         if(length>B.length) return 1;
379         if(length<B.length) return -1;
380         for(int i=vec.size()-1;i>=0;--i)
381             if(vec[i]>B[i])return 1;
382             else if(vec[i]<B[i]) return -1;
383         return 0;
384     }
385 
386     protected:
387 
388     inline void    clear_zero()
389     //This func deletes leading zero
390     {
391         while(!vec[vec.size()-1] && vec.size()!=1)
392             vec.pop_back();
393         return ;
394     }
395 
396     /***************************************************************/
397     //CALL THIS FUNCTION AFTER EVERY OPERATION TO MAKE ANSWER CORRECT
398 #ifndef SAFE_CALC_MODE
399     inline void    update_length()
400     //fixup length and leading zero
401     {
402         clear_zero();
403         if(vec.size()==1 && vec[0]==0) length=1;
404         else if(vec[vec.size()-1]/100)length=vec.size()*3;
405         else if(vec[vec.size()-1]/10)length=vec.size()*3-1;
406         else length=vec.size()*3-2;
407         return ;
408     }
409 #else
410     //fixup length and leading zero
411     inline void    update_length()
412     {
413         clear_zero();
414         length=vec.size(); return ;
415     }
416 #endif
417     /***************************************************************/
418 
419     //carry the vec
420     //notice: call update_length() after calling this func
421     inline void    Go_up()
422     {
423         int t=vec.size();
424         for(int i=0;i<t-1;++i)
425         {
426             vec[i+1]+=vec[i]/DIGITS;
427             vec[i]%=DIGITS;
428         }
429         while(vec[t-1]>=DIGITS)
430             vec.push_back(vec[t-1]/DIGITS),vec[t-1]%=DIGITS,t++;
431         return ;
432     }
433 
434     //resize the vector
435     inline void    resize(int x) { vec.resize(x); }
436 
437     inline int    get_quotient(_this_class& R,_this_class& B,
438             _this_class* Map)
439     //This func get a quotient for divide operator by dichotomy
440     {
441         if(R.compare_abs(B)<0) return 0;
442         int l=0,r=DIGITS,mid;
443         while(l<r-1)
444         {
445             mid=l+((r-l)>>1);
446             if(mid && Map[mid].size()==1 && Map[mid][0]==0)
447                 Map[mid]=B*mid;
448             int t=R.compare_abs(Map[mid]);
449             if(t>0)l=mid;
450             else if(t<0)r=mid;
451             else { l=mid; break; }
452         }
453         if(mid && Map[l].size()==1 && Map[l][0]==0) Map[l]=B*l;
454         R=R-Map[l];
455         return l;
456     }
457 
458 
459     private:
460 
461     inline _this_class positive_add(_this_class& B)
462     //This func returns Abs(*this)+Abs(B)
463     //calling this func must garantee '*this' and 'B' are both positive
464     {    
465         _this_class C;//ans
466         bool _Longer_vec;
467 
468         if(vec.size()>B.size())    _Longer_vec=1;
469         else            _Longer_vec=0;
470 
471         //if B is shorter
472         if(_Longer_vec)
473         {
474             C.resize(vec.size()+1);
475             //add shorter digits first
476             for(int i=0;i<(int)B.size();++i)
477             {
478                 C[i+1]=(C[i]+vec[i]+B[i])/DIGITS;
479                 C[i]=(C[i]+vec[i]+B[i])%DIGITS;
480             }//each saves 3 digits
481 
482             //calc rest digits
483             for(int i=B.size();i<(int)vec.size();++i)
484             {
485                 C[i+1]=(C[i]+vec[i])/DIGITS;
486                 C[i]=(C[i]+vec[i])%DIGITS;
487             }
488         }
489         //if B is longer
490         else 
491         {
492             C.resize(B.size()+1);
493             //add shorter digits first
494             for(int i=0;i<(int)vec.size();++i)
495             {
496                 C[i+1]=(C[i]+vec[i]+B[i])/DIGITS;
497                 C[i]=(C[i]+vec[i]+B[i])%DIGITS;
498             }//each saves 3 digits
499 
500             //calc rest digits
501             for(int i=vec.size();i<(int)B.size();++i)
502             {
503                 C[i+1]=(C[i]+B[i])/DIGITS;
504                 C[i]=(C[i]+B[i])%DIGITS;
505             }
506         }
507         C.update_length();
508         return C;
509     }
510 
511     inline _this_class positive_minus(_this_class& B) 
512     //This func returns Abs(*this)-Abs(B)
513     //calling this func must garantee '*this > B'
514     {
515         _this_class C;//ans
516         C.resize(vec.size());
517         //calc first B.size() digits
518         for(int i=0;i<(int)B.size();++i)
519         {
520             if(vec[i]+C[i]<B[i])C[i]+=DIGITS+vec[i]-B[i],C[i+1]--;
521             else C[i]+=vec[i]-B[i];
522         }
523         //copy the rest digits
524         for(int i=B.size();i<(int)vec.size();++i)
525             C[i]+=vec[i];
526         C.update_length();
527         return C;
528     }
529 
530     inline _this_class positive_muliply(_this_class& B)
531     //This func returns Abs(*this)*Abs(B)
532     {
533         _this_class C=*this;
534 
535         double temp=log(vec.size()+B.size())/log(2);
536 
537         if((vec.size()+B.size())*temp<vec.size()*B.size())
538         //Using fast Fourier transform if (n+m)log(n+m)<n*m
539         //to speed mul operation when data become huge
540         {
541             _fast_Fourier_transform F;
542             C.vec=F.multi(C.vec,B.vec);
543         }
544         else
545         //Using normal O(n*m) algorithm when n,m is small
546         {
547             _normal_mul F;
548             if(vec.size()<B.size())C.vec=F.multi(C.vec,B.vec);
549             else C.vec=F.multi(B.vec,C.vec);
550         }
551         
552         C.Go_up();
553         C.update_length();
554         return C;
555     }
556 
557     inline _this_class positive_divide(_this_class& B)
558     //This func returns Abs(*this)/Abs(B)
559     {
560         if(B.length==1 && B.vec[0]==0) throw Divide_By_Zero_Error();
561         _this_class C;
562         _this_class r;//Remainder
563 
564         _this_class Map[DIGITS+2];
565         //save B*x to save time.
566 
567         //if dividend is less return 0
568         if(compare_abs(B)<0) return C;
569 
570         //if dividend is equal to divisor return 1
571         if(compare_abs(B)==0) { C[0]=1; return C; }
572 
573         C.resize(vec.size());
574         r.resize(B.size());
575         for(int i=B.size()-2;i>=0;--i)
576             r[i]=vec[vec.size()-B.size()+1+i];
577         r.update_length();
578 
579         for(int i=vec.size()-B.size();i>=0;--i)
580         {
581             r*=DIGITS; r[0]+=vec[i]; r.update_length();
582             //dichotomy
583             int t=get_quotient(r,B,Map);
584             C[i]=t;
585         }
586         C.update_length();
587         return C;
588     }
589 
590     inline _this_class positive_mod(_this_class& B)
591     //This func returns Abs(*this)%Abs(B)
592     {
593         if(B.length==1 && B.vec[0]==0) throw Divide_By_Zero_Error();
594         _this_class r;//Remainder
595 
596         _this_class Map[DIGITS+2];
597         //save B*x to save time.
598 
599         //if dividend is less return vec
600         if(compare_abs(B)<0) return *this;
601 
602         //if dividend is equal to divisor return 1
603         if(compare_abs(B)==0) return r;
604 
605         r.resize(B.size());
606         for(int i=B.size()-2;i>=0;--i)
607             r[i]=vec[vec.size()-B.size()+1+i];
608         r.update_length();
609 
610         for(int i=vec.size()-B.size();i>=0;--i)
611         {
612             r*=DIGITS; r[0]+=vec[i]; r.update_length();
613             //dichotomy
614             get_quotient(r,B,Map);
615         }
616         return r;
617     }
618 };
619 
620 //Use This Class in your program.
621 class BigN
622 {
623     public:
624 #ifdef    SAFE_CALC_MODE
625     //You may NOT modify the digits directly.
626     //if number has NO x-th number, function will return -1
627     inline int    operator[](const int x) { return _data.getkth(x); }
628     //This Func change x-th digit to y.(start from 0th,high digit)
629     //Returns false for failure, true for success.
630     inline bool    modify(const int x,const int y)
631     { return _data.modify(x,y); }
632 #endif
633 
634     //Fix -0 to 0
635     inline void    Fix_zero() { _data.fix_zero(); }
636     
637     inline BigN    operator = (const int B)
638     { _data=B; Fix_zero(); return *this;}
639     inline BigN    operator = (const char* B)
640     { _data=B; Fix_zero(); return *this;}
641 
642     inline BigN    operator + (BigN B)
643     { B._data=_data+B._data; B.Fix_zero(); return B; }
644     inline BigN    operator - (BigN B)
645     { B._data=_data-B._data; B.Fix_zero(); return B; }
646     inline BigN    operator * (BigN B)
647     { B._data=_data*B._data; B.Fix_zero(); return B; }
648     inline BigN    operator / (BigN B)
649     { B._data=_data/B._data; B.Fix_zero(); return B; }
650     inline BigN    operator % (BigN B)
651     { B._data=_data%B._data; B.Fix_zero(); return B; }
652     inline BigN    operator + (int B)
653     { BigN C=B; C._data=_data+C._data; C.Fix_zero(); return C; }
654     inline BigN    operator - (int B)
655     { BigN C=B; C._data=_data-C._data; C.Fix_zero(); return C; }
656     inline BigN    operator * (int B)
657     { BigN C=B; C._data=_data*C._data; C.Fix_zero(); return C; }
658     inline BigN    operator / (int B)
659     { BigN C=B; C._data=_data/C._data; C.Fix_zero(); return C; }
660     inline BigN    operator % (int B)
661      { BigN C=B; C._data=_data%C._data; C.Fix_zero(); return C; }
662     inline BigN operator+=(BigN B)
663     { _data+=B._data; Fix_zero(); return *this; }
664     inline BigN operator-=(BigN B)
665     { _data-=B._data; Fix_zero(); return *this; }
666     inline BigN operator*=(BigN B)
667     { _data*=B._data; Fix_zero(); return *this; }
668     inline BigN operator/=(BigN B)
669     { _data/=B._data; Fix_zero(); return *this; }
670     inline BigN operator%=(BigN B)
671     { _data%=B._data; Fix_zero(); return *this; }
672     inline BigN operator+=(int B) 
673     { _data+=B; Fix_zero(); return *this; }
674     inline BigN operator-=(int B) 
675     { _data-=B; Fix_zero(); return *this; }
676     inline BigN operator*=(int B) 
677     { _data*=B; Fix_zero(); return *this; }
678     inline BigN operator/=(int B) 
679     { _data/=B; Fix_zero(); return *this; }
680     inline BigN operator%=(int B) 
681     { _data%=B; Fix_zero(); return *this; }
682 
683     inline bool    operator < (BigN B)
684     {
685         if(_data.is_positive() && B._data.is_positive())
686             return _data.compare_abs(B._data)<0;
687         if(_data.is_negetive() && B._data.is_negetive())
688             return _data.compare_abs(B._data)>0;
689         if(_data.is_positive() && B._data.is_negetive()) return false;
690         return true;
691     }
692     inline bool    operator > (BigN B)
693     {
694         if(_data.is_positive() && B._data.is_positive())
695             return _data.compare_abs(B._data)>0;
696         if(_data.is_negetive() && B._data.is_negetive())
697             return _data.compare_abs(B._data)<0;
698         if(_data.is_positive() && B._data.is_negetive()) return true;
699         return false;
700     }
701     inline bool    operator == (BigN B)
702     {
703         if(_data.is_positive()!=B._data.is_positive()) return 0;
704         else return _data.compare_abs(B._data)==0;
705     }
706     inline bool    operator <= (BigN B) { return *this<B || *this==B; }
707     inline bool    operator >= (BigN B) { return *this>B || *this==B; }
708     inline bool    operator != (BigN B) { return !(*this==B); }
709 
710     inline bool    operator < (int B) { return *this<(BigN)B; }
711     inline bool    operator > (int B) { return *this>(BigN)B; }
712     inline bool    operator <= (int B) { return *this<=(BigN)B; }
713     inline bool    operator >= (int B) { return *this>=(BigN)B; }
714     inline bool    operator != (int B) { return *this!=(BigN)B; }
715     inline bool    operator == (int B) { return *this==(BigN)B; }
716 
717 
718     inline void    print() { _data.print(); }
719     inline void    printn() { _data.print(); printf("
"); }
720 
721 
722     //These two functions both return std::string-type of the number.
723     //If it is the first time you try to get the string after an operation,
724     //you should use getstr(), for function str() will return the old
725     //string.
726     //Each time you call getstr(), the string will up-to-date.
727     //And you can use str(), after calling getstr() to save time.
728     inline std::string getstr(){ _data.print_to_str(_Str); return _Str; }
729     inline std::string str() { return _Str; }
730 
731     protected:
732     std::string _Str;
733     inline void    refresh_str() { _data.print_to_str(_Str); }
734 
735     private:
736     //this class contains real data and does the exact calculation
737     typedef _data_container_of_BigN _data_class;
738     _data_class _data;
739     public:
740     BigN() {}
741     BigN(const int x) { _data=x; }
742     BigN(const char* x) { _data=x; }
743 };
744 
745 BigN operator + (int A,BigN B) { return B+A; }
746 BigN operator * (int A,BigN B) { return B*A; }
747 
748 /***************************************************************************/
749 
750 char     a[1100000],b[1100000];
751 
752 int main()
753 {
754     scanf("%s%s",a,b);
755     BigN x=a,y=b,T;
756     printf("a+b="); (x+y).printn();
757     printf("a-b="); (x-y).printn();
758     printf("a*b="); (x*y).printn();
759     printf("a/b="); (x/y).printn();
760     printf("a%%b="); (x%y).printn();
761     printf("a*1000+b="); (T=x*1000+y).printn();
762     printf("2nd digit=%c
",T.getstr().c_str()[2]);
763 
764     //These operation need definition of SAFE_CALC_MODE in line 33
765 
766     //T.modify(3,9);
767     //printf("after modify 3rd digit to 9="); T.printn();
768     //printf("3rd digit=");printf("%d
",T[3]);
769     //printf("after unavailable operatorion="); T.modify(100,9);
770     //T.printn();
771     //printf("unavailable access="); printf("%d
",T[100]);
772 
773     /*****************************************************/
774     //      Input:                                       //
775     //              123 45                               //
776     //      Output:                                      //
777     //              a+b=168                              //
778     //              a-b=78                               //
779     //              a*b=5535                             //
780     //              a/b=2                                //
781     //              a%b=33                               //
782     //              a*1000+b=123045                      //
783     //              2nd digit=3                          //
784     //              after modify 3rd digit to 9=123945   //
785     //              3rd digit=9                          //
786     //              after unavailable operatorion=123945 //
787     //              unavailable access=-1                //
788     /*****************************************************/
789     return 0;
790 }
[ C++ 快速高精度模板 ] [ BigN类 ] 大整数类 高精度 模板 BigInt FFT 快速傅里叶变换

[ C++ 快速高精度模板 ] [ BigN类 ] 大整数类高精度模板 BigInt FFT 快速傅里叶变换
