(维护)高精模板(缺除法)

2018-06-27 10:02:08来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

2018-6-2

特殊版(vector动态数组存)

  1 #pragma GCC optimize("Ofast")
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 using namespace std;
  8 #define pb push_back
  9 typedef long long LL;
 10 typedef int B_INT;
 11 #define p_c "%04d"
 12 #define i_c "%d"
 13 #define b_c "10000"
 14 //const char p_c[]="%08lld";
 15 //const char i_c[]="%lld";
 16 //const char b_c[]="100000000";
 17 const B_INT p=4;//压p位,int压4位加乘法可能导致溢出,longlong压8位乘法会炸而且慢
 18 const B_INT base=10000;//压p位,最大数为10^p-1
 19 const int maxl=31000;//如果有乘法,则大于最大读入位数/p*2
 20 //fft乘容易掉精度,不能压太多位
 21 //const B_INT l2b=14;//=向上取整(log2(base))
 22 const B_INT l2b=13;//=向下取整(log2(base))
 23 const int fftlen=33000;//32768>31000且为2的幂
 24 struct Bigint
 25 {
 26 #define TRY(a,x) {if((a).size()<(x)+1){    B_INT k=0;while((1<<(k+1))<=((x)+1))++k;a.resize(1<<(k+1));}}
 27 /*
 28 基本类型(char,int,float,double等)的静态成员可以在类里面声明并初始化,
 29 非基本类(char[],string ,自定义等)必须在类里面声明,类外初始化。
 30 */
 31     vector<B_INT> a;
 32     Bigint(){a.pb(0);}//a[0]->len,a[i]->从后往前数第i个p位;0的长度为0
 33     Bigint(const char *str){*this=str;}
 34     Bigint(const Bigint& b){a=b.a;}
 35     Bigint(int x){*this=x;}
 36 
 37     Bigint& operator=(const Bigint& b){a=b.a;return *this;}
 38     Bigint& operator=(int x)
 39     {
 40         a.clear();a.pb(0);
 41         while(x){++a[0];a.pb(x%base);x/=base;}
 42         return *this;
 43     }
 44     Bigint& operator=(const char *str)
 45     {
 46         a.clear();a.pb(0);
 47         B_INT k=0,p=1;const char *str1=(str+strlen(str)-1);
 48         while(str1>=str)
 49         {
 50             k=k+p*(*str1-48);
 51             if(p==base){++a[0];a.pb(k%base);k/=base;p=1;}
 52             --str1;p*=10;
 53         }
 54         ++a[0];a.pb(k);
 55         while(a[0]&&a[a[0]]==0)    --a[0];
 56         //vector<B_INT> t=a;swap(t,a);
 57         return *this;
 58     }
 59 
 60     friend Bigint operator+(const Bigint&,const Bigint&);
 61     friend Bigint& operator+=(Bigint&,const Bigint&);
 62     friend Bigint operator+(const Bigint&,int x);
 63     friend Bigint& operator+=(Bigint&,int x);
 64 
 65     friend Bigint operator-(const Bigint&,const Bigint&);
 66     friend Bigint& operator-=(Bigint&,const Bigint&);
 67 
 68     friend Bigint operator*(const Bigint&,const Bigint&);
 69     friend Bigint& operator*=(Bigint&,const Bigint&);
 70     friend Bigint operator*(const Bigint&,int x);
 71     friend Bigint& operator*=(Bigint& a,int x);
 72 
 73     friend Bigint operator/(const Bigint&,const Bigint&);
 74     friend Bigint& operator/=(Bigint&,const Bigint&);
 75     friend Bigint operator/(const Bigint& a,int x);
 76     friend Bigint& operator/=(Bigint &,int);
 77 
 78     friend Bigint operator%(const Bigint&,const Bigint&);
 79 
 80     friend bool operator<(const Bigint& a,const Bigint& b);
 81     friend bool operator<=(const Bigint& a,const Bigint& b);
 82     friend bool operator>(const Bigint& a,const Bigint& b);
 83     friend bool operator>=(const Bigint& a,const Bigint& b);
 84     friend bool operator==(const Bigint& a,const Bigint& b);
 85     friend bool operator!=(const Bigint& a,const Bigint& b);
 86 
 87     void print() const
 88     {
 89         printf(i_c,a[a[0]]);
 90         for(B_INT i=a[0]-1;i>0;i--)
 91             printf(p_c,a[i]);
 92     }
 93     void println() const    {print();puts("");}
 94     void println(const char* x) const   {print();puts(x);}
 95     bool odd() const    {return a[0]?(a[1]&1):0;}
 96 };
 97 LL buf[maxl<<1];
 98 const double Pi=acos(-1.0);
 99 struct cpl
100 {
101     double x,y;
102     cpl(double xx=0,double yy=0):x(xx),y(yy){}
103 };
104 cpl operator+(const cpl& a,const cpl& b){return cpl(a.x+b.x,a.y+b.y);}
105 cpl operator-(const cpl& a,const cpl& b){return cpl(a.x-b.x,a.y-b.y);}
106 cpl operator*(const cpl& a,const cpl& b){return cpl(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
107 int rev[fftlen];cpl t1[fftlen],t2[fftlen];
108 void dft(cpl *a,int len,int idx)//将a做dft,结果放入a,dft->idx=1,idft->idx=-1
109 {
110     cpl wn,wnk,t1,t2;int i,j,k;
111     for(i=0;i<len;i++)    if(i<rev[i])    swap(a[i],a[rev[i]]);
112     //例如将23的二进制(10111)翻转(共5位),先得到01011(后四位)的翻转(11010),然后右移一位后在前面补上一个1(因为23&1为1)
113     for(i=1;i<len;i<<=1)
114     {
115         wn=cpl(cos(Pi/i),idx*sin(Pi/i));
116         for(j=0;j<len;j+=(i<<1))//每一次合并[j,j+i),[j+i,j+2i)
117         {
118             wnk=cpl(1,0);
119             for(k=j;k<j+i;k++)
120             {
121                 t1=a[k];t2=wnk*a[k+i];
122                 a[k]=t1+t2;a[k+i]=t1-t2;
123                 wnk=wnk*wn;
124             }
125         }
126     }
127     if(idx==-1)
128         for(i=0;i<len;i++)
129             a[i].x/=len,a[i].y/=len;
130 }
131 const Bigint zero=0,one=1;
132 //const Bigint bas=base;
133 //const Bigint pw2[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
134 const B_INT pw22[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
135 bool operator<(const Bigint& a,const Bigint& b)
136 {
137     if(a.a[0]!=b.a[0])
138         return a.a[0]<b.a[0];
139     for(B_INT i=a.a[0];i>0;i--)
140         if(a.a[i]!=b.a[i])
141             return a.a[i]<b.a[i];
142     return 0;//相等
143 }
144 /*
145 非静态成员函数后面加const(加到非成员函数或静态成员后面会产生编译错误),
146 表示成员函数隐含传入的this指针为 const指针,
147 决定了在该成员函数中,
148 任意修改它所在的类的成员的操作都是不允许的
149 (因为隐含了对this指针的const引用);
150 唯一的例外是对于 mutable修饰的成员。
151 加了const的成员函数可以被非const对象和const对象调用,
152 但不加const的成员函数只能被非const对象调用。
153 下方b是const,const函数不能修改其数据成员
154 */
155 bool operator>(const Bigint& a,const Bigint& b)
156 {
157     return b<a;
158     /*
159     if(a.a[0]!=b.a[0])
160         return a.a[0]>b.a[0];
161     for(int i=a.a[0];i>0;i--)
162         if(a.a[i]!=b.a[i])
163             return a.a[i]>b.a[i];
164     return false;//相等
165     */
166 }
167 bool operator<=(const Bigint& a,const Bigint& b)
168 {
169     return !(b<a);
170     /*
171     if(a.a[0]!=b.a[0])
172         return a.a[0]>b.a[0];
173     for(int i=a.a[0];i>0;i--)
174         if(a.a[i]!=b.a[i])
175             return a.a[i]>b.a[i];
176     return true;//相等
177     */
178 }
179 bool operator>=(const Bigint& a,const Bigint& b)
180 {
181     return !(a<b);
182     /*
183     if(a.a[0]!=b.a[0])
184         return a.a[0]>b.a[0];
185     for(int i=a.a[0];i>0;i--)
186         if(a.a[i]!=b.a[i])
187             return a.a[i]>b.a[i];
188     return true;//相等
189     */
190 }
191 bool operator==(const Bigint& a,const Bigint& b)
192 {
193     if(a.a[0]!=b.a[0])
194         return 0;
195     for(B_INT i=a.a[0];i>0;--i)
196         if(a.a[i]!=b.a[i])
197             return 0;
198     return 1;
199 }
200 bool operator!=(const Bigint& a,const Bigint& b)
201 {
202     return !(a==b);
203 }
204 Bigint operator+(const Bigint& a,const Bigint& b){Bigint c=a;c+=b;return c;}
205 Bigint& operator+=(Bigint& a,const Bigint& b)
206 {
207     B_INT i;
208     a.a[0]=max(a.a[0],b.a[0]);
209     TRY(a.a,a.a[0]+1);
210     for(i=1;i<=a.a[0];++i)
211     {
212         if(i<=b.a[0])    a.a[i]+=b.a[i];
213         a.a[i+1]+=a.a[i]/base;
214         a.a[i]%=base;
215     }
216     if(a.a[a.a[0]+1]>0) ++a.a[0];
217     return a;
218 }
219 Bigint operator+(const Bigint& a,int x){Bigint c=a;c+=x;return c;}
220 Bigint& operator+=(Bigint& a,int x)
221 {
222     B_INT i;
223     if(x>=base)    return a+=Bigint(x);
224     TRY(a.a,a.a[0]+1);
225     a.a[1]+=x;
226     for(i=1;i<=a.a[0];++i)
227         if(a.a[i]>=base)    {++a.a[i+1];a.a[i]-=base;}
228         else    break;
229     if(a.a[a.a[0]+1]>0) ++a.a[0];
230     return a;
231 }
232 Bigint operator-(const Bigint& a,const Bigint& b){Bigint c=a;c-=b;return c;}
233 Bigint& operator-=(Bigint &a,const Bigint &b)//要求保证减数b小于等于被减数a
234 {
235     B_INT i;
236     a.a[0]=max(a.a[0],b.a[0]);
237     //TRY(a.a,a.a[0]+1);//b<=a,所以减完后位数不可能增多
238     for(i=1;i<=min(a.a[0],b.a[0]);++i)    a.a[i]-=b.a[i];
239     for(i=1;i<=a.a[0];++i)
240         if(a.a[i]<0)    {a.a[i]+=base;a.a[i+1]--;}
241     while(a.a[0]&&a.a[a.a[0]]==0)    --a.a[0];
242     //vector<B_INT> t=a.a;swap(t,a.a);
243     return a;
244 }
245 Bigint operator*(const Bigint& a,const Bigint& b){Bigint c=a;c*=b;return c;}
246 Bigint& operator*=(Bigint& a,const Bigint& b)
247 {
248     if(a==zero||b==zero)    {return a=zero;}
249     int i,len=a.a[0]+b.a[0]-1,bit=0;
250     while((1<<bit)<len)    bit++;
251     len=(1<<bit);
252     for(i=0;i<len;++i)
253         rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
254     for(i=1;i<=a.a[0];++i)
255         t1[i-1].x=a.a[i],t1[i-1].y=0;
256     for(i=a.a[0];i<len;++i)
257         t1[i].x=t1[i].y=0;
258     for(i=1;i<=b.a[0];++i)
259         t2[i-1].x=b.a[i],t2[i-1].y=0;
260     for(i=b.a[0];i<len;++i)
261         t2[i].x=t2[i].y=0;
262     dft(t1,len,1);dft(t2,len,1);
263     for(i=0;i<len;++i)  t1[i]=t1[i]*t2[i];
264     dft(t1,len,-1);
265     for(i=1;i<=len;++i)   buf[i]=(LL)(t1[i-1].x+0.5);
266     buf[len+1]=0;//
267     for(i=1;i<=len;++i)
268     {
269         buf[i+1]+=buf[i]/base;
270         buf[i]%=base;
271     }
272     if(buf[len+1])  ++len;
273     while(buf[len]==0)  --len;
274     a.a[0]=len;
275     TRY(a.a,len);
276     for(i=1;i<=len;i++) a.a[i]=buf[i];
277     return a;
278 }
279 Bigint operator*(const Bigint& a,int x){Bigint c=a;c*=x;return c;}
280 Bigint& operator*=(Bigint& a,int x)
281 {
282     if(x==0)    return a=zero;
283     if(x>=base)    return a*=Bigint(x);
284     B_INT i;
285     //a[a[0]+1]=0
286     memset(buf,0,sizeof(buf));
287     for(i=1;i<=a.a[0];++i)
288     {
289         //printf("%d %d\n",i,a.a[i]);
290         buf[i]=(LL)a.a[i]*x;//注意LL
291         //a.a[i+1]+=buf[0]/base;
292         //a.a[i]=buf[i]%base;//printf("%daa\n",a.a[i]);
293     }
294     for(i=1;i<=a.a[0];++i)
295     {
296         //printf("%lldss\n",buf[i]);
297         a.a[i]=buf[i]%base;
298         buf[i+1]+=buf[i]/base;
299     }
300     //if(a.a[a.a[0]+1]>0)    ++a.a[0];
301     //if(buf[buf[0]+1]>0) {a.a[++a.a[0]]=buf[buf[0]+1];}
302     if(buf[a.a[0]+1]>0)    {++a.a[0];a.a.pb(buf[a.a[0]]);}
303     return a;
304 }
305 Bigint operator/(const Bigint& a,const Bigint& b)
306 {
307     if(a<b) return zero;//必须加这句
308     Bigint t=zero,c,d;c.a[0]=a.a[0]-b.a[0]+1;TRY(c.a,c.a[0]);
309     B_INT i,j;
310     for(i=a.a[0];i>=1;--i)
311     {
312        t*=base;t+=a.a[i];
313        for(j=l2b;j>=0;--j)
314        {
315            d=b*pw22[j];
316            if(t>=d)    {c.a[i]+=pw22[j];t-=d;}
317        }
318        //printf("%dt2\n",c.a[i]);
319     }
320     while(c.a[0]&&c.a[c.a[0]]==0) --c.a[0];
321     //vector<B_INT> t=c.a;swap(t,c.a);
322     return c;
323 }
324 Bigint& operator/=(Bigint& a,const Bigint& b){a=a/b;return a;}
325 Bigint operator/(const Bigint& a,int x){Bigint c=a;c/=x;return c;}
326 Bigint& operator/=(Bigint& a,int x)//要求不超过base的小数字
327 {
328     B_INT i;LL t=0;
329     for(i=a.a[0];i>=1;--i)
330     {
331         t*=base;t+=a.a[i];// int xx;printf("%lldkfk\n",t);
332         a.a[i]=t/x;//printf("%dkfk\n",a.a[i]);scanf("%d",&xx);
333         t%=x;
334     }
335     while(a.a[0]&&a.a[a.a[0]]==0) --a.a[0];
336     return a;
337 }
338 Bigint operator%(const Bigint& a,const Bigint& b)
339 {
340     //return *this-*this/b*b;
341     Bigint t=zero,d;
342     B_INT i,j;
343     for(i=a.a[0];i>=1;--i)
344     {
345         t=t*base+a.a[i];
346         for(j=l2b;j>=0;--j)
347         {
348             d=b*pw22[j];
349             if(t>=d)    t-=d;
350         }
351     }
352     return t;
353 }
354 void swap(Bigint &a,Bigint &b)    {swap(a.a,b.a);}
355 Bigint x[3];
356 char str[100010];
357 Bigint gcd(Bigint a,Bigint b)
358 {
359     Bigint c=one;
360     while(a!=b)
361     {
362         if(a<b) swap(a,b);
363         //(a/2).println("k2");
364         //a.print();puts("a");b.print();puts("b");puts("");
365         if(a.odd()&&b.odd())  a-=b;
366         else    if(a.odd())
367             b/=2;
368         else if(b.odd())
369             a/=2;
370         else
371             a/=2,b/=2,c*=2;
372         //a.print();puts("a2");b.print();puts("b2");puts("");c.println("c2");int t;scanf("%d",&t);
373     }
374     return a*c;
375 }
376 //Bigint gcd(Bigint a,Bigint b)
377 //{
378 //    Bigint t;
379 //    static Bigint zero=0;
380 //    while(b!=zero)
381 //    {
382 //        t=a;
383 //        a=b;
384 //        b=t%b;
385 //    }
386 //    return a;
387 //}
388 int main()
389 {
390     /*
391     bool fl;int t;//scanf("%d",&t);
392     //(Bigint("13582583")*15345).print();
393     //(Bigint("3948636459042352478494043859377305164061320248669026579423660")).println();
394     //(Bigint("3948636459042352478494043859377305164061320248669026579423660")/Bigint("2")).println();
395     while(scanf("%s",str+1)==1)
396     {
397         fl=0;
398         if(str[1]=='-') x[0]=str+2,fl^=1;
399         else    x[0]=str+1;
400         scanf("%s",str+1);
401         if(str[1]=='-') x[1]=str+2,fl^=1;
402         else    x[1]=str+1;
403         //(x[0]+x[1]).println();
404         //if(x[0]>=x[1])  (x[0]-x[1]).println();
405         //else    putchar('-'),(x[1]-x[0]).println();
406         //x[0].println();x[1].println();
407         x[2]=x[0]*x[1];
408         if(fl&&x[2]!=zero)  putchar('-');
409         x[2].println();
410         //(x[0]/x[1]).println();
411         //(x[0]%x[1]).println();
412     }
413     //(gcd(x[0],x[1])).print();;
414     //(x[0]*x[1]).print();
415     //(Bigint("8392523")%Bigint("5")).print();
416     //printf("\n%d",(Bigint("233")-Bigint("233"))==Bigint("1"));
417     */
418     scanf("%s",str);
419     x[0]=str;
420     scanf("%s",str);
421     x[1]=str;
422     //(x[0]+x[1]).println();
423     //if(x[0]>=x[1])  (x[0]-x[1]).println();
424     //else    putchar('-'),(x[1]-x[0]).println();
425     //(x[0]*x[1]).println();
426     //(x[0]/x[1]).println();
427     //(x[0]%x[1]).println();
428     gcd(x[0],x[1]).println();
429     return 0;
430 }
View Code

2018-3-4

(加入FFT优化的高精度乘法)

注意:对拍得出,两个乘数在80000位及以下保持压4位应该不会出现精度问题,乘数在80000到390000位则只能压3位或以下(只测了几组随机数据的精度,所以位数超过10000最好还是只压3位)

带注释版本:

  1 #pragma GCC optimize("Ofast")
  2 #pragma GCC target("sse3","sse2","sse")
  3 #pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
  4 #pragma GCC target("f16c")
  5 //#pragma GCC target("fma","avx2")
  6 //#pragma GCC target("xop","fma4")
  7 #pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
  8 #pragma GCC diagnostic error "-fwhole-program"
  9 #pragma GCC diagnostic error "-fcse-skip-blocks"
 10 #pragma GCC diagnostic error "-funsafe-loop-optimizations"
 11 #pragma GCC diagnostic error "-std=c++14"
 12 #include<cstdio>
 13 #include<cstring>
 14 #include<algorithm>
 15 #include<cmath>
 16 using namespace std;
 17 typedef long long LL;
 18 typedef int B_INT;
 19 #define p_c "%04d"
 20 #define i_c "%d"
 21 #define b_c "10000"
 22 //const char p_c[]="%08lld";
 23 //const char i_c[]="%lld";
 24 //const char b_c[]="100000000";
 25 const B_INT p=4;//压p位,int压4位加乘法可能导致溢出,longlong压8位乘法会炸而且慢
 26 const B_INT base=10000;//压p位,最大数为10^p-1
 27 const int maxl=31000;//如果有乘法,则大于最大读入位数/p*2
 28 //fft乘容易掉精度,不能压太多位
 29 //const B_INT l2b=14;//=向上取整(log2(base))
 30 const B_INT l2b=13;//=向下取整(log2(base))
 31 const int fftlen=33000;//4096>4000且为2的幂
 32 struct Bigint
 33 {
 34 /*
 35 基本类型(char,int,float,double等)的静态成员可以在类里面声明并初始化,
 36 非基本类(char[],string ,自定义等)必须在类里面声明,类外初始化。
 37 */
 38     B_INT a[maxl];//a[0]->len,a[i]->从后往前数第i个p位
 39     Bigint(){memset(a,0,sizeof(a));}
 40     Bigint(const char *str){*this=str;}
 41     Bigint(const Bigint& b){memcpy(a,b.a,sizeof(a));}
 42     Bigint(int x){*this=x;}
 43 
 44     Bigint& operator=(const Bigint& b){memcpy(a,b.a,sizeof(a));return *this;}
 45     Bigint& operator=(int x)
 46     {
 47         memset(a,0,sizeof(a));
 48         do{a[++a[0]]=x%base;x/=base;}while(x);
 49         return *this;
 50     }
 51     Bigint& operator=(const char *str)
 52     {
 53         memset(a,0,sizeof(a));
 54         B_INT k=0,p=1;char *str1=(char*)(str+strlen(str)-1);
 55         while(str1>=str)
 56         {
 57             k=k+p*(*str1-48);
 58             if(p==base){a[++a[0]]=k%base;k/=base;p=1;}
 59             --str1;p*=10;
 60         }
 61         a[++a[0]]=k;
 62         return *this;
 63     }
 64 
 65     friend Bigint operator+(const Bigint&,const Bigint&);
 66     friend Bigint& operator+=(Bigint&,const Bigint&);
 67     friend Bigint operator+(const Bigint&,int x);
 68     friend Bigint& operator+=(Bigint&,int x);
 69 
 70     friend Bigint operator-(const Bigint&,const Bigint&);
 71     friend Bigint& operator-=(Bigint&,const Bigint&);
 72 
 73     friend Bigint operator*(const Bigint&,const Bigint&);
 74     friend Bigint& operator*=(Bigint&,const Bigint&);
 75     friend Bigint operator*(const Bigint&,int x);
 76     friend Bigint& operator*=(Bigint& a,int x);
 77 
 78     friend Bigint operator/(const Bigint&,const Bigint&);
 79     friend Bigint& operator/=(Bigint&,const Bigint&);
 80     friend Bigint operator/(const Bigint& a,int x);
 81     friend Bigint& operator/=(Bigint &,int);
 82 
 83     friend Bigint operator%(const Bigint&,const Bigint&);
 84 
 85     friend bool operator<(const Bigint& a,const Bigint& b);
 86     friend bool operator<=(const Bigint& a,const Bigint& b);
 87     friend bool operator>(const Bigint& a,const Bigint& b);
 88     friend bool operator>=(const Bigint& a,const Bigint& b);
 89     friend bool operator==(const Bigint& a,const Bigint& b);
 90     friend bool operator!=(const Bigint& a,const Bigint& b);
 91 
 92     void print() const
 93     {
 94         printf(i_c,a[a[0]]);
 95         for(B_INT i=a[0]-1;i>0;i--)
 96             printf(p_c,a[i]);
 97     }
 98     void println() const    {print();puts("");}
 99     void println(const char* x) const   {print();puts(x);}
100     bool odd() const    {return a[1]&1;}
101 };
102 LL buf[maxl<<1];
103 const double Pi=acos(-1.0);
104 struct cpl
105 {
106     double x,y;
107     cpl(double xx=0,double yy=0):x(xx),y(yy){}
108 };
109 cpl operator+(const cpl& a,const cpl& b){return cpl(a.x+b.x,a.y+b.y);}
110 cpl operator-(const cpl& a,const cpl& b){return cpl(a.x-b.x,a.y-b.y);}
111 cpl operator*(const cpl& a,const cpl& b){return cpl(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
112 int rev[fftlen];cpl t1[fftlen],t2[fftlen];
113 void dft(cpl *a,int len,int idx)//将a做dft,结果放入a,dft->idx=1,idft->idx=-1
114 {
115     cpl wn,wnk,t1,t2;int i,j,k;
116     for(i=0;i<len;i++)    if(i<rev[i])    swap(a[i],a[rev[i]]);
117     //例如将23的二进制(10111)翻转(共5位),先得到01011(后四位)的翻转(11010),然后右移一位后在前面补上一个1(因为23&1为1)
118     for(i=1;i<len;i<<=1)
119     {
120         wn=cpl(cos(Pi/i),idx*sin(Pi/i));
121         for(j=0;j<len;j+=(i<<1))//每一次合并[j,j+i),[j+i,j+2i)
122         {
123             wnk=cpl(1,0);
124             for(k=j;k<j+i;k++)
125             {
126                 t1=a[k];t2=wnk*a[k+i];
127                 a[k]=t1+t2;a[k+i]=t1-t2;
128                 wnk=wnk*wn;
129             }
130         }
131     }
132     if(idx==-1)
133         for(i=0;i<len;i++)
134             a[i].x/=len,a[i].y/=len;
135 }
136 const Bigint zero=0,one=1;
137 //const Bigint bas=base;
138 //const Bigint pw2[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
139 const B_INT pw22[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
140 bool operator<(const Bigint& a,const Bigint& b)
141 {
142     if(a.a[0]!=b.a[0])
143         return a.a[0]<b.a[0];
144     for(B_INT i=a.a[0];i>0;i--)
145         if(a.a[i]!=b.a[i])
146             return a.a[i]<b.a[i];
147     return 0;//相等
148 }
149 /*
150 非静态成员函数后面加const(加到非成员函数或静态成员后面会产生编译错误),
151 表示成员函数隐含传入的this指针为 const指针,
152 决定了在该成员函数中,
153 任意修改它所在的类的成员的操作都是不允许的
154 (因为隐含了对this指针的const引用);
155 唯一的例外是对于 mutable修饰的成员。
156 加了const的成员函数可以被非const对象和const对象调用,
157 但不加const的成员函数只能被非const对象调用。
158 下方b是const,const函数不能修改其数据成员
159 */
160 bool operator>(const Bigint& a,const Bigint& b)
161 {
162     return b<a;
163     /*
164     if(a.a[0]!=b.a[0])
165         return a.a[0]>b.a[0];
166     for(int i=a.a[0];i>0;i--)
167         if(a.a[i]!=b.a[i])
168             return a.a[i]>b.a[i];
169     return false;//相等
170     */
171 }
172 bool operator<=(const Bigint& a,const Bigint& b)
173 {
174     return !(b<a);
175     /*
176     if(a.a[0]!=b.a[0])
177         return a.a[0]>b.a[0];
178     for(int i=a.a[0];i>0;i--)
179         if(a.a[i]!=b.a[i])
180             return a.a[i]>b.a[i];
181     return true;//相等
182     */
183 }
184 bool operator>=(const Bigint& a,const Bigint& b)
185 {
186     return !(a<b);
187     /*
188     if(a.a[0]!=b.a[0])
189         return a.a[0]>b.a[0];
190     for(int i=a.a[0];i>0;i--)
191         if(a.a[i]!=b.a[i])
192             return a.a[i]>b.a[i];
193     return true;//相等
194     */
195 }
196 bool operator==(const Bigint& a,const Bigint& b)
197 {
198     if(a.a[0]!=b.a[0])
199         return 0;
200     for(B_INT i=a.a[0];i>0;--i)
201         if(a.a[i]!=b.a[i])
202             return 0;
203     return 1;
204 }
205 bool operator!=(const Bigint& a,const Bigint& b)
206 {
207     return !(a==b);
208 }
209 Bigint operator+(const Bigint& a,const Bigint& b){Bigint c=a;c+=b;return c;}
210 Bigint& operator+=(Bigint& a,const Bigint& b)
211 {
212     B_INT i;
213     a.a[0]=max(a.a[0],b.a[0]);
214     for(i=1;i<=a.a[0];i++)
215     {
216         a.a[i]+=b.a[i];
217         a.a[i+1]+=a.a[i]/base;
218         a.a[i]%=base;
219     }
220     if(a.a[a.a[0]+1]>0) a.a[0]++;
221     return a;
222 }
223 Bigint operator+(const Bigint& a,int x){Bigint c=a;c+=x;return c;}
224 Bigint& operator+=(Bigint& a,int x)//要求不超过base的小数字
225 {
226     B_INT i;
227     a.a[1]+=x;
228     for(i=1;i<=a.a[0];++i)
229         if(a.a[i]>=base)    {++a.a[i+1];a.a[i]-=base;}
230         else    break;
231     if(a.a[a.a[0]+1]>0) ++a.a[0];
232     return a;
233 }
234 Bigint operator-(const Bigint& a,const Bigint& b){Bigint c=a;c-=b;return c;}
235 Bigint& operator-=(Bigint &a,const Bigint &b)//要求保证减数小于被减数
236 {
237     B_INT i;
238     a.a[0]=std::max(a.a[0],b.a[0]);
239     for(i=1;i<=a.a[0];++i)    a.a[i]-=b.a[i];
240     for(i=1;i<=a.a[0];++i)
241         if(a.a[i]<0)    {a.a[i]+=base;a.a[i+1]--;}
242     while(a.a[a.a[0]]==0&&a.a[0]>1)    --a.a[0];
243     return a;
244 }
245 Bigint operator*(const Bigint& a,const Bigint& b){Bigint c=a;c*=b;return c;}
246 Bigint& operator*=(Bigint& a,const Bigint& b)
247 {
248     if(a==zero||b==zero)    {return a=zero;}
249     int i,len=a.a[0]+b.a[0]-1,bit=0;
250     while((1<<bit)<len)    bit++;
251     len=(1<<bit);
252     for(i=0;i<len;++i)
253         rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
254     for(i=1;i<=a.a[0];++i)
255         t1[i-1].x=a.a[i],t1[i-1].y=0;
256     for(i=a.a[0];i<len;++i)
257         t1[i].x=t1[i].y=0;
258     for(i=1;i<=b.a[0];++i)
259         t2[i-1].x=b.a[i],t2[i-1].y=0;
260     for(i=b.a[0];i<len;++i)
261         t2[i].x=t2[i].y=0;
262     dft(t1,len,1);dft(t2,len,1);
263     for(i=0;i<len;++i)  t1[i]=t1[i]*t2[i];
264     dft(t1,len,-1);
265     for(i=1;i<=len;++i)   buf[i]=(LL)(t1[i-1].x+0.5);
266     buf[len+1]=0;//
267     for(i=1;i<=len;++i)
268     {
269         buf[i+1]+=buf[i]/base;
270         buf[i]%=base;
271     }
272     if(buf[len+1])  ++len;
273     while(buf[len]==0)  --len;
274     a.a[0]=len;
275     for(i=1;i<=len;i++) a.a[i]=buf[i];
276     return a;
277 }
278 Bigint operator*(const Bigint& a,int x){Bigint c=a;c*=x;return c;}
279 Bigint& operator*=(Bigint& a,int x)//要求不超过base的小数字
280 {
281     if(x==0)    {a=zero;return a;}
282     B_INT i;
283     //a[a[0]+1]=0
284     memset(buf,0,sizeof(buf));
285     for(i=1;i<=a.a[0];++i)
286     {
287         //printf("%d %d\n",i,a.a[i]);
288         buf[i]=(LL)a.a[i]*x;//注意LL
289         //a.a[i+1]+=buf[0]/base;
290         //a.a[i]=buf[i]%base;//printf("%daa\n",a.a[i]);
291     }
292     for(i=1;i<=a.a[0];++i)
293     {
294         //printf("%lldss\n",buf[i]);
295         a.a[i]=buf[i]%base;
296         buf[i+1]+=buf[i]/base;
297     }
298     //if(a.a[a.a[0]+1]>0)    ++a.a[0];
299     //if(buf[buf[0]+1]>0) {a.a[++a.a[0]]=buf[buf[0]+1];}
300     if(buf[a.a[0]+1]>0)    {++a.a[0];a.a[a.a[0]]=buf[a.a[0]];}
301     return a;
302 }
303 Bigint operator/(const Bigint& a,const Bigint& b)
304 {
305     if(a<b) return zero;//必须加这句
306     Bigint t=zero,c,d;c.a[0]=a.a[0]-b.a[0]+1;
307     B_INT i,j;
308     for(i=a.a[0];i>=1;--i)
309     {
310        t*=base;t+=a.a[i];
311        for(j=l2b;j>=0;--j)
312        {
313            d=b*pw22[j];
314            if(t>=d)    {c.a[i]+=pw22[j];t-=d;}
315        }
316        //printf("%dt2\n",c.a[i]);
317     }
318     while(c.a[0]>1&&c.a[c.a[0]]==0) --c.a[0];
319     return c;
320 }
321 Bigint& operator/=(Bigint& a,const Bigint& b){a=a/b;return a;}
322 Bigint operator/(const Bigint& a,int x){Bigint c=a;c/=x;return c;}
323 Bigint& operator/=(Bigint& a,int x)//要求不超过base的小数字
324 {
325     B_INT i;LL t=0;
326     for(i=a.a[0];i>=1;--i)
327     {
328         t*=base;t+=a.a[i];// int xx;printf("%lldkfk\n",t);
329         a.a[i]=t/x;//printf("%dkfk\n",a.a[i]);scanf("%d",&xx);
330         t%=x;
331     }
332     while(a.a[0]>1&&a.a[a.a[0]]==0) --a.a[0];
333     return a;
334 }
335 Bigint operator%(const Bigint& a,const Bigint& b)
336 {
337     //return *this-*this/b*b;
338     Bigint t=zero,d;
339     B_INT i,j;
340     for(i=a.a[0];i>=1;--i)
341     {
342         t=t*base+a.a[i];
343         for(j=l2b;j>=0;--j)
344         {
345             d=b*pw22[j];
346             if(t>=d)    t-=d;
347         }
348     }
349     return t;
350 }
351 
352 Bigint x[3];
353 char str[50010];
354 Bigint gcd(Bigint a,Bigint b)
355 {
356     Bigint c=one,t;
357     while(a!=b)
358     {
359         if(a<b) {t=a;a=b;b=t;}
360         //(a/2).println("k2");
361         //a.print();puts("a");b.print();puts("b");puts("");
362         if(a.odd()&&b.odd())  a-=b;
363         else    if(a.odd())
364             b/=2;
365         else if(b.odd())
366             a/=2;
367         else
368             a/=2,b/=2,c*=2;
369         //a.print();puts("a2");b.print();puts("b2");puts("");c.println("c2");int t;scanf("%d",&t);
370     }
371     return a*c;
372 }
373 //Bigint gcd(Bigint a,Bigint b)
374 //{
375 //    Bigint t;
376 //    static Bigint zero=0;
377 //    while(b!=zero)
378 //    {
379 //        t=a;
380 //        a=b;
381 //        b=t%b;
382 //    }
383 //    return a;
384 //}
385 int main()
386 {
387     bool fl;int t;scanf("%d",&t);
388     //(Bigint("13582583")*15345).print();
389     //(Bigint("3948636459042352478494043859377305164061320248669026579423660")).println();
390     //(Bigint("3948636459042352478494043859377305164061320248669026579423660")/Bigint("2")).println();
391     while(scanf("%s",str+1)==1)
392     {
393         fl=0;
394         if(str[1]=='-') x[0]=str+2,fl^=1;
395         else    x[0]=str+1;
396         scanf("%s",str+1);
397         if(str[1]=='-') x[1]=str+2,fl^=1;
398         else    x[1]=str+1;
399         //(x[0]+x[1]).println();
400         //if(x[0]>=x[1])  (x[0]-x[1]).println();
401         //else    putchar('-'),(x[1]-x[0]).println();
402         //x[0].println();x[1].println();
403         x[2]=x[0]*x[1];
404         if(fl&&x[2]!=zero)  putchar('-');
405         x[2].println();
406         //(x[0]/x[1]).println();
407         //(x[0]%x[1]).println();
408     }
409     //(gcd(x[0],x[1])).print();;
410     //(x[0]*x[1]).print();
411     //(Bigint("8392523")%Bigint("5")).print();
412     //printf("\n%d",(Bigint("233")-Bigint("233"))==Bigint("1"));
413 //    scanf("%s",str);
414 //    x[0]=str;
415 //    scanf("%s",str);
416 //    x[1]=str;
417 //  if(x[0]<x[1])
418 //  {
419 //      printf("-");
420 //      x[2]=x[0];
421 //      x[0]=x[1];
422 //      x[1]=x[2];
423 //  }
424 //  (x[0]-x[1]).print();
425 //  (x[0]*x[1]).print();
426 //    printf("%d",x[0]>x[1]);
427 //    (x[1]=x[1]).print();
428 //  puts("");
429 //  x[0].print();
430 //  puts("");
431 //  x[1].print();
432     return 0;
433 }
View Code

压行版本:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
typedef int B_INT;
#define p_c "%04d"
#define i_c "%d"
#define b_c "10000"
const B_INT p=4,base=10000,l2b=13;
const int maxl=5100,fftlen=8200;
struct Bigint{
B_INT a[maxl];
Bigint(){memset(a,0,sizeof(a));}
Bigint(const char *str){*this=str;}
Bigint(const Bigint& b){memcpy(a,b.a,sizeof(a));}
Bigint(int x){*this=x;}
Bigint& operator=(const Bigint& b){memcpy(a,b.a,sizeof(a));return *this;}
Bigint& operator=(int x){memset(a,0,sizeof(a));do{a[++a[0]]=x%base;x/=base;}while(x);return *this;}
Bigint& operator=(const char *str){memset(a,0,sizeof(a));
B_INT k=0,p=1;char *str1=(char*)(str+strlen(str)-1);
while(str1>=str){k=k+p*(*str1-48);if(p==base){a[++a[0]]=k%base;k/=base;p=1;}--str1;p*=10;}
a[++a[0]]=k;return *this;}
friend Bigint operator+(const Bigint&,const Bigint&);
friend Bigint& operator+=(Bigint&,const Bigint&);
friend Bigint operator+(const Bigint&,int x);
friend Bigint& operator+=(Bigint&,int x);
friend Bigint operator-(const Bigint&,const Bigint&);
friend Bigint& operator-=(Bigint&,const Bigint&);
friend Bigint operator*(const Bigint&,const Bigint&);
friend Bigint& operator*=(Bigint&,const Bigint&);
friend Bigint operator*(const Bigint&,int x);
friend Bigint& operator*=(Bigint& a,int x);
friend Bigint operator/(const Bigint&,const Bigint&);
friend Bigint& operator/=(Bigint&,const Bigint&);
friend Bigint operator/(const Bigint& a,int x);
friend Bigint& operator/=(Bigint &,int);
friend Bigint operator%(const Bigint&,const Bigint&);
friend bool operator<(const Bigint& a,const Bigint& b);
friend bool operator<=(const Bigint& a,const Bigint& b);
friend bool operator>(const Bigint& a,const Bigint& b);
friend bool operator>=(const Bigint& a,const Bigint& b);
friend bool operator==(const Bigint& a,const Bigint& b);
friend bool operator!=(const Bigint& a,const Bigint& b);
void print()const{printf(i_c,a[a[0]]);for(B_INT i=a[0]-1;i>0;i--)printf(p_c,a[i]);}
void println()const{print();puts("");}
void println(const char* x)const{print();puts(x);}
bool odd()const{return a[1]&1;}};
LL buf[maxl<<1];const double Pi=acos(-1.0);
struct cpl{double x,y;cpl(double xx=0,double yy=0):x(xx),y(yy){}};
cpl operator+(const cpl& a,const cpl& b){return cpl(a.x+b.x,a.y+b.y);}
cpl operator-(const cpl& a,const cpl& b){return cpl(a.x-b.x,a.y-b.y);}
cpl operator*(const cpl& a,const cpl& b){return cpl(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int rev[fftlen];cpl t1[fftlen],t2[fftlen];
void dft(cpl *a,int len,int idx){cpl wn,wnk,t1,t2;int i,j,k;
for(i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(i=1;i<len;i<<=1){wn=cpl(cos(Pi/i),idx*sin(Pi/i));for(j=0;j<len;j+=(i<<1))
{wnk=cpl(1,0);for(k=j;k<j+i;k++){t1=a[k];t2=wnk*a[k+i];a[k]=t1+t2;a[k+i]=t1-t2;wnk=wnk*wn;}}}
if(idx==-1)for(i=0;i<len;i++)a[i].x/=len,a[i].y/=len;}
const Bigint zero=0,one=1;const B_INT pw22[]={1,2,4,8,16,32,64,128,256,512,1024,
2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
bool operator<(const Bigint& a,const Bigint& b){if(a.a[0]!=b.a[0])return a.a[0]<b.a[0];
for(B_INT i=a.a[0];i>0;i--)if(a.a[i]!=b.a[i])return a.a[i]<b.a[i];return 0;}
bool operator>(const Bigint& a,const Bigint& b){return b<a;}
bool operator<=(const Bigint& a,const Bigint& b){return !(b<a);}
bool operator>=(const Bigint& a,const Bigint& b){return !(a<b);}
bool operator==(const Bigint& a,const Bigint& b){if(a.a[0]!=b.a[0])return 0;
for(B_INT i=a.a[0];i>0;--i)if(a.a[i]!=b.a[i])return 0;return 1;}
bool operator!=(const Bigint& a,const Bigint& b){return !(a==b);}
Bigint& operator+=(Bigint& a,const Bigint& b){B_INT i;a.a[0]=max(a.a[0],b.a[0]);
for(i=1;i<=a.a[0];i++){a.a[i]+=b.a[i];a.a[i+1]+=a.a[i]/base;a.a[i]%=base;}if(a.a[a.a[0]+1]>0) a.a[0]++;return a;}
Bigint operator+(const Bigint& a,const Bigint& b){Bigint c=a;c+=b;return c;}
Bigint operator+(const Bigint& a,int x){Bigint c=a;c+=x;return c;}
Bigint& operator+=(Bigint& a,int x){B_INT i;a.a[1]+=x;
for(i=1;i<=a.a[0];++i)if(a.a[i]>=base){++a.a[i+1];a.a[i]-=base;}else    break;
if(a.a[a.a[0]+1]>0) ++a.a[0];return a;}
Bigint& operator-=(Bigint &a,const Bigint &b){B_INT i;a.a[0]=std::max(a.a[0],b.a[0]);
for(i=1;i<=a.a[0];++i)a.a[i]-=b.a[i];for(i=1;i<=a.a[0];++i)if(a.a[i]<0){a.a[i]+=base;a.a[i+1]--;}
while(a.a[a.a[0]]==0&&a.a[0]>1)--a.a[0];return a;}
Bigint operator-(const Bigint& a,const Bigint& b){Bigint c=a;c-=b;return c;}
Bigint operator*(const Bigint& a,const Bigint& b){Bigint c=a;c*=b;return c;}
Bigint& operator*=(Bigint& a,const Bigint& b){if(a==zero||b==zero){return a=zero;}
int i,len=a.a[0]+b.a[0]-1,bit=0;while((1<<bit)<len)bit++;len=(1<<bit);
for(i=0;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
for(i=1;i<=a.a[0];++i)t1[i-1].x=a.a[i],t1[i-1].y=0;for(i=a.a[0];i<len;++i)t1[i].x=t1[i].y=0;
for(i=1;i<=b.a[0];++i)t2[i-1].x=b.a[i],t2[i-1].y=0;for(i=b.a[0];i<len;++i)t2[i].x=t2[i].y=0;
dft(t1,len,1);dft(t2,len,1);for(i=0;i<len;++i)t1[i]=t1[i]*t2[i];dft(t1,len,-1);
for(i=1;i<=len;++i)buf[i]=(LL)(t1[i-1].x+0.5);buf[len+1]=0;for(i=1;i<=len;++i)
{buf[i+1]+=buf[i]/base;buf[i]%=base;}if(buf[len+1])++len;while(buf[len]==0)--len;
a.a[0]=len;for(i=1;i<=len;i++) a.a[i]=buf[i];return a;}
Bigint operator*(const Bigint& a,int x){Bigint c=a;c*=x;return c;}
Bigint& operator*=(Bigint& a,int x){if(x==0){a=zero;return a;}B_INT i;memset(buf,0,sizeof(buf));
for(i=1;i<=a.a[0];++i)buf[i]=(LL)a.a[i]*x;for(i=1;i<=a.a[0];++i){a.a[i]=buf[i]%base;buf[i+1]+=buf[i]/base;}
if(buf[a.a[0]+1]>0){++a.a[0];a.a[a.a[0]]=buf[a.a[0]];}return a;}
Bigint operator/(const Bigint& a,const Bigint& b){if(a<b) return zero;Bigint t=zero,c,d;
c.a[0]=a.a[0]-b.a[0]+1;B_INT i,j;for(i=a.a[0];i>=1;--i){t*=base;t+=a.a[i];for(j=l2b;j>=0;--j)
{d=b*pw22[j];if(t>=d){c.a[i]+=pw22[j];t-=d;}}}while(c.a[0]>1&&c.a[c.a[0]]==0) --c.a[0];return c;}
Bigint& operator/=(Bigint& a,const Bigint& b){a=a/b;return a;}
Bigint operator/(const Bigint& a,int x){Bigint c=a;c/=x;return c;}
Bigint& operator/=(Bigint& a,int x){B_INT i;LL t=0;for(i=a.a[0];i>=1;--i)
{t*=base;t+=a.a[i];a.a[i]=t/x;t%=x;}while(a.a[0]>1&&a.a[a.a[0]]==0)--a.a[0];return a;}
Bigint operator%(const Bigint& a,const Bigint& b){Bigint t=zero,d;B_INT i,j;
for(i=a.a[0];i>=1;--i){t=t*base+a.a[i];for(j=l2b;j>=0;--j){d=b*pw22[j];if(t>=d)t-=d;}}return t;}
Bigint gcd(Bigint a,Bigint b){Bigint c=one,t;while(a!=b){if(a<b) {t=a;a=b;b=t;}if(a.odd()&&b.odd())    a-=b;
else if(a.odd()) b/=2;else if(b.odd())a/=2;else a/=2,b/=2,c*=2;}return a*c;}
Bigint x[3];
char str[30010];
int main()
{
    scanf("%s",str);x[0]=str;
    scanf("%s",str);x[1]=str;
    (x[0]+x[1]).println();
    if(x[0]>=x[1])  (x[0]-x[1]).println();
    else    putchar('-'),(x[1]-x[0]).println();
    (x[0]*x[1]).println();
    (x[0]/x[1]).println();
    (x[0]%x[1]).println();
    return 0;
}

2018-2-6

附:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;

namespace BigNumber{
    const int L=5010,Base=10000,Bit=4;
    const LL MaxInt=2147483647;
    const int Pw10[15]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
    const int Pw2[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};

    LL DOF[L];

    struct BigNum{
        int v[L],le,flag;
        BigNum(){
            memset(v,0,sizeof v); le=flag=1;
        }
        BigNum(int x){
            flag=1; le=1; memset(v,0,sizeof v);
            if (x<0) flag=-1,x=-x;
            v[1]=x;
            while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le;
        }
        BigNum(LL x){
            flag=1; le=1; memset(v,0,sizeof v);
            if (x<0) flag=-1,x=-x;
            v[1]=x%Base; v[2]=x/Base%Base;
            v[3]=x/Base/Base%Base; v[4]=x/Base/Base/Base;
            le=4;
            while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le;
            while (v[le]==0 && le>1) --le;
        }
        BigNum(int len,int fir){
            memset(v,0,sizeof v);
            le=len; v[le]=fir; flag=1;
        }
        BigNum(const BigNum &a,int x){
            memset(v,0,sizeof v);
            le=a.le+x; flag=a.flag;
            for (int i=1;i<=a.le;++i) v[i+x]=a.v[i];
        }
        int IntoInt(){
            if (le>3) cerr <<"Error: cannot change so big into int!"<<endl;
            LL d=0;
            for (int i=le;i>=1;--i) d=d*Base+v[i];
            if (flag==-1) d=-d;
            if (d>MaxInt || -d<MaxInt+1) cerr <<"Error: cannot change so big into int!"<<endl;
            return d;
        }

        void Clear(){
            memset(v,0,sizeof v); le=flag=1;
        }
        void operator =(int a){
            *this = BigNum(a);
        }
        void operator =(LL a){
            *this = BigNum(a);
        }


        //Compare -->
        bool operator ==(const BigNum &a)const{
            if (le!=a.le || flag!=a.flag) return 0;
            for (int i=1;i<=le;++i) if (v[i]!=a.v[i]) return 0;
            return 1;
        }
        bool operator <(const BigNum &a)const{
            if (flag<a.flag || flag==a.flag && le<a.le) return 1;
            if (flag>a.flag || flag==a.flag && le>a.le) return 0;
            for (int i=le;i>=1;--i){
                if (v[i]<a.v[i]) return flag==1? 1:0;
                if (v[i]>a.v[i]) return flag==1? 0:1;
            }return 0;
        }
        bool operator >(const BigNum &a)const{
            if (flag<a.flag || flag==a.flag && le<a.le) return 0;
            if (flag>a.flag || flag==a.flag && le>a.le) return 1;
            for (int i=le;i>=1;--i){
                if (v[i]<a.v[i]) return flag==1? 0:1;
                if (v[i]>a.v[i]) return flag==1? 1:0;
            }return 0;
        }
        bool operator ==(const int &x)const{
            return *this == BigNum(x);
        }


        //Add and Sub -->
        void operator +=(const BigNum &x){
            BigNum a=*this; BigNum b=x; memset(v,0,sizeof v);
            flag=1;
            if (a.flag==-1 && b.flag==-1){
                flag=-1; a.flag=1; b.flag=1;
            }
            if (a < b) swap(a,b);
            if (b.flag==-1){
                b.flag=1;
                if (a < b) swap(a,b),flag=-1;
                b.flag=-1;
            }
            if (b.flag==1){
                le=a.le;
                for (int i=1;i<=le;++i) v[i]=a.v[i]+b.v[i];
                for (int i=1;i<=le;++i) v[i+1]+=v[i]/Base,v[i]%=Base;
                while (v[le+1]>0) ++le;
            }else{
                le=a.le;
                for (int i=1;i<=le;++i) v[i]=a.v[i]-b.v[i];
                for (int i=1;i<=le;++i) if (v[i]<0) --v[i+1],v[i]+=Base;
                while (v[le]==0 && le>1) --le;
            }
        }
        void operator +=(int x){
            *this += BigNum(x);
        }
        void operator -=(const BigNum &x){
            BigNum a=x; a.flag=-a.flag;
            *this += a;
        }
        void operator -=(int x){
            *this -= BigNum(x);
        }


        BigNum &operator ++(){
            return *this += 1, *this;
        }
        BigNum &operator --(){
            return *this -= 1, *this;
        }
        BigNum operator ++(int){
            BigNum c(*this);
            ++ *this; return c;
        }
        BigNum operator --(int){
            BigNum c(*this);
            -- *this; return c;
        }


        //Mul -->
        void operator *=(const BigNum &x){
            BigNum a=x;
            if (flag==a.flag) flag=1;else flag=-1;
            a.flag=1;

            memset(DOF,0,sizeof DOF);
            for (int i=1;i<=le;++i)
                for (int j=1;j<=a.le;++j)
                    DOF[i+j-1]+=v[i]*a.v[j];
            le+=a.le+9;
            for (int i=1;i<=le;++i) DOF[i+1]+=DOF[i]/Base,DOF[i]%=Base;
            while (DOF[le]==0 && le>1) --le;
            for (int i=1;i<=le;++i) v[i]=DOF[i];
        }
        void operator *=(const int &x){
            *this *= BigNum(x);
        }
        void operator *=(const LL &x){
            *this *= BigNum(x);
        }


        //Div -->
        void operator /=(int x){
            if (x==0){
                cerr <<"Error: div 0!"; return;
            }
            BigNum a; a=x;
            if (flag==a.flag) flag=1;else flag=-1;
            a.flag=1;

            memset(DOF,0,sizeof DOF);
            LL rest=0;
            for (int i=le;i>=1;--i){
                rest=rest*Base+v[i];
                DOF[i]=rest/x; rest%=x;
                v[i]=0;
            }
            for (int i=le;i>=1;--i) v[i]=DOF[i];
            while (v[le]==0 && le>1) --le;
        }
        void operator /=(const BigNum &x){
            if (x==0){
                cerr <<"Error: div 0!"; return;
            }
            BigNum a=*this,b=x,c,d;
            if (a.flag==b.flag) flag=1;else flag=-1;
            for (int i=le;i>0;--i) v[i]=0;
            le=a.le-b.le+1;

            for (int i=le;i>=1;--i){
                c=BigNum(b,i-1);
                for (int j=log2(Base);j>=0;--j){
                    d=c; d*=Pw2[j];
                    if (!(a < d)) v[i]+=Pw2[j],a-=d;
                }
            }
            for (int i=1;i<=le;++i) v[i+1]+=v[i]/Base,v[i]%=Base;
            while (v[le+1]>0) ++le;
            while (v[le]==0 && le>1) --le;
        }


        //Mod -->
        void operator %=(int p){
            if (p==0){
                cerr <<"Error: mod 0!"; return;
            }
            LL d=0; if (p < 0) p=-p;
            for (int i=le;i>=1;--i) d=(d*Base+v[i])%p,v[i]=0;
            le=1; v[1]=d;
            while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le;
        }

        void operator %=(const BigNum &x){
            if (x==0){
                cerr <<"Error: mod 0!"; return;
            }
            BigNum a=*this,b=x,c,d;
            for (int i=le;i>0;--i) v[i]=0;
            le=a.le-b.le+1;

            for (int i=le;i>=1;--i){
                c=BigNum(b,i-1);
                for (int j=log2(Base);j>=0;--j){
                    d=c; d*=Pw2[j];
                    if (!(a < d)) a-=d;
                }
            }
            *this = a;
        }


        //Power -->
        BigNum pow(int b){
            BigNum a,c; a=*this; c=1;
            for (;b;b>>=1,a*=a) if (b&1) c*=a;
            return c;
        }
        BigNum pow(int x,int b){
            BigNum c,a; c=1; a=x;
            for (;b;b>>=1,a*=a) if (b&1) c*=x;
            return c;
        }
        int pow2(int a,int b){
            int c=1;
            for (;b;b>>=1,a*=a) if (b&1) c*=a;
            return c;
        }


        //Shr and Shl -->
        void operator <<=(int x){
            if (x<=30) *this *= pow2(2,x);
                else *this *= pow(2,x);
        }
        void operator >>=(int x){
            if (x<=30) *this /= pow2(2,x);
                else *this /= pow(2,x);
        }
    };


    //Compare -->
    bool operator ==(const int &a,const BigNum &b){
        return b == a;
    }
    bool operator !=(const BigNum &a,const BigNum &b){
        return !(a == b);
    }
    bool operator !=(const BigNum &a,const int &b){
        return !(a == b);
    }
    bool operator !=(const int &a,const BigNum &b){
        return !(b == a);
    }


    bool operator <(const BigNum &a,const int &b){
        return a < BigNum(b);
    }
    bool operator <(const int &a,const BigNum &b){
        return BigNum(a) < b;
    }
    bool operator >(const BigNum &a,const int &b){
        return a > BigNum(b);
    }
    bool operator >(const int &a,const BigNum &b){
        return BigNum(a) > b;
    }
    bool operator <=(const BigNum &a,const BigNum &b){
        if (a > b) return 0; return 1;
    }
    bool operator >=(const BigNum &a,const BigNum &b){
        if (a < b) return 0; return 1;
    }
    bool operator <=(const BigNum &a,const int &b){
        if (a > b) return 0; return 1;
    }
    bool operator <=(const int &a,const BigNum &b){
        if (a > b) return 0; return 1;
    }
    bool operator >=(const BigNum &a,const int &b){
        if (a < b) return 0; return 1;
    }
    bool operator >=(const int &a,const BigNum &b){
        if (a < b) return 0; return 1;
    }


    int max(const int &a,const int &b){
        if (a < b) return b; return a;
    }
    int min(const int &a,const int &b){
        if (a < b) return a; return b;
    }
    BigNum max(const BigNum &a,const BigNum &b){
        if (a < b) return b; return a;
    }
    BigNum min(const BigNum &a,const BigNum &b){
        if (a < b) return a; return b;
    }


    //Add -->
    BigNum operator +(const BigNum &a,const BigNum &b){
        BigNum c=a; c+=b; return c;
    }
    BigNum operator +(const BigNum &a,const int &b){
        BigNum c=a; c+=b; return c;
    }
    BigNum operator +(const int &a,const BigNum &b){
        BigNum c=b; c+=a; return c;
    }


    //Sub -->
    BigNum operator -(const BigNum &a,const BigNum &b){
        BigNum c=a; c-=b; return c;
    }
    BigNum operator -(const BigNum &a,const int &b){
        BigNum c=a; c-=b; return c;
    }
    BigNum operator -(const int &a,const BigNum &b){
        BigNum c=b; c-=a; return c;
    }


    //Mul -->
    BigNum operator *(const BigNum &a,const BigNum &b){
        BigNum c=a; c*=b; return c;
    }
    BigNum operator *(const BigNum &a,const int &b){
        BigNum c=a; c*=b; return c;
    }
    BigNum operator *(const int &a,const BigNum &b){
        BigNum c=b; c*=a; return c;
    }


    //Div -->
    BigNum operator /(const BigNum &a,const int &b){
        BigNum c=a; c/=b; return c;
    }
    BigNum operator /(const int &a,const BigNum &b){
        BigNum c=b; c/=a; return c;
    }
    BigNum operator /(const BigNum &a,const BigNum &b){
        BigNum c=a; c/=b; return c;
    }


    //Mod -->
    BigNum operator %(const BigNum &a,const int &b){
        BigNum c=a; c%=b; return c;
    }
    BigNum operator %(const int &a,const BigNum &b){
        BigNum c=b; c%=a; return c;
    }
    BigNum operator %(const BigNum &a,const BigNum &b){
        BigNum c=a; c%=b; return c;
    }

    //Shr and Shl -->
    BigNum operator <<(const BigNum &a,const int b){
        BigNum c=a; c<<=b; return c;
    }
    BigNum operator <<(const BigNum &a,BigNum &b){
        return a << b.IntoInt();
    }
    BigNum operator >>(const BigNum &a,const int &b){
        BigNum c=a; c>>=b; return c;
    }
    BigNum operator >>(const BigNum &a,BigNum &b){
        return a >> b.IntoInt();
    }


    //Abs -->
    BigNum abs(const BigNum &x){
        BigNum c=x; c.flag=1; return c;
    }


    //Odd -->
    int odd(const BigNum &x){
        if (x.v[1] & 1) return 1; return 0;
    }


    //Gcd -->
    BigNum gcd(const BigNum &x,const BigNum &y){
        BigNum a=x,b=y,c=BigNum(1);
        while (a!=b){
            if (a < b) swap(a,b);
            if (odd(a) && odd(b)) a-=b; else
            if (odd(a)) b/=2; else
            if (odd(b)) a/=2; else
                a/=2,b/=2,c*=2;
        }return a*c;
    }


    //Sqrt -->
    BigNum sqrt(const BigNum &x){
        if (x<0){
            cerr <<"Error: sqrt nagetive!";
            return 0;
        }
        BigNum l,r,m,A;
        l=BigNum(x.le/2,1); r=BigNum(x.le/2+2,1);
        while (l<=r){
            m=(l+r)>>1;
            if (m*m<=x) A=m,l=m+1; else r=m-1;
        }return A;
    }
    BigNum sqrt(const BigNum &a,int b){
        BigNum x=a;
        if (x<0 && b%2==0){
            cerr <<"Error: sqrt nagetive!";
            return 0;
        }
        BigNum l,r,m,A;
        int frog=x.flag; x.flag=1;
        l=0; r=1;
        while (r.pow(b)<x) l=r,r*=2;
        while (l<=r){
            m=(l+r)>>1;
            if (m.pow(b)<=x) A=m,l=m+1; else r=m-1;
        }
        if (frog==-1) A.flag=-1;
        return A;
    }


    //Read and Print -->
    string yz; char cyz;
    void Read(BigNum &a){
        a.Clear();
        while (cin.peek()==' ') getchar();
        if (cin.peek()=='-'){
            a.flag=-1; cin >>cyz;
        }
        cin >>yz;
        int len=yz.length();
        a.le=len/Bit;
        for (int i=1;i<=a.le;++i){
            int l=len-Bit*i,r=l+Bit-1;
            for (int j=l;j<=r;++j) a.v[i]=a.v[i]*10+yz[j]-'0';
        }
        if(len%Bit!=0){
            int r=len-Bit*a.le-1;
            ++a.le;
            for (int j=0;j<=r;++j) a.v[a.le]=a.v[a.le]*10+yz[j]-'0';
        }
    }

    void PrintWith(int x,int k){
        for (int i=k-1;i>=0;--i) if (Pw10[i]>x) putchar('0');
            else putchar(x/Pw10[i]+'0'),x%=Pw10[i];
    }
    void Print(const BigNum &a){
        if (a.flag==-1) putchar('-');
        printf("%d",a.v[a.le]);
        for (int i=a.le-1;i>=1;--i) PrintWith(a.v[i],Bit);
    }
    void Println(const BigNum &a){
        Print(a); puts("");
    }
};
using namespace BigNumber;



int main() {
    BigNum a,b,c,d;
    Read(a); Read(b);
    Println(gcd(a,b));
    return 0;
}
View Code

奇怪的东西:

//#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;typedef long long LL;typedef int X;
#define p_c "%05d"
#define i_c "%d"
#define b_c "100000"
#define M memcpy
#define E memset
#define R return
#define C const
#define O operator
#define F for
#define Q printf
#define L bool
#define S sizeof
C X p=5,e=100000;C int maxl=4000,l2b=16;
struct B{X a[maxl];
B(){E(a,0,S(a));}B(C char *str){*this=str;}B(C B& b){M(a,b.a,S(a));}
B(int x){*this=x;}B& O=(C B& b){M(a,b.a,S(a));R *this;}
B& O=(int x){E(a,0,S(a));do{a[++a[0]]=x%e;x/=e;}while(x);R *this;}
B& O=(C char *str){E(a,0,S(a));X k=0,p=1;char *str1=(char*)(str+strlen(str)-1);
while(str1>=str){k=k+p*(*str1-48);if(p==e){a[++a[0]]=k%e;k/=e;p=1;}--str1;p*=10;}a[++a[0]]=k;R *this;}
void P()C{Q(i_c,a[a[0]]);F(X i=a[0]-1;i>0;i--)Q(p_c,a[i]);}
void println()C{P();puts("");}void println(C char* x) C{P();puts(x);}L odd() C{R a[1]&1;}};
LL buf[maxl<<1];C B z=0,one=1;
C X pw22[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
L O<(C B& a,C B& b){if(a.a[0]!=b.a[0])R a.a[0]<b.a[0];F(X i=a.a[0];i>0;i--)if(a.a[i]!=b.a[i])R a.a[i]<b.a[i];R 0;}
L O>(C B& a,C B& b){R b<a;}L O<=(C B& a,C B& b){R !(b<a);}L O>=(C B& a,C B& b){R !(a<b);}
L O==(C B& a,C B& b){if(a.a[0]!=b.a[0])R 0;F(X i=a.a[0];i>0;--i)if(a.a[i]!=b.a[i])R 0;R 1;}
L O!=(C B& a,C B& b){R !(a==b);}
B& O+=(B& a,C B& b){X i;a.a[0]=max(a.a[0],b.a[0]);
F(i=1;i<=a.a[0];i++){a.a[i]+=b.a[i];a.a[i+1]+=a.a[i]/e;a.a[i]%=e;}if(a.a[a.a[0]+1]>0) a.a[0]++;R a;}
B O+(C B& a,C B& b){B c=a;c+=b;R c;}B O+(C B& a,int x){B c=a;c+=x;R c;}
B& O+=(B& a,int x){X i;a.a[1]+=x;
F(i=1;i<=a.a[0];++i)if(a.a[i]>=e){++a.a[i+1];a.a[i]-=e;}else break;if(a.a[a.a[0]+1]>0) ++a.a[0];R a;}
B& O-=(B &a,C B &b){X i;a.a[0]=max(a.a[0],b.a[0]);
F(i=1;i<=a.a[0];++i)a.a[i]-=b.a[i];F(i=1;i<=a.a[0];++i)if(a.a[i]<0){a.a[i]+=e;a.a[i+1]--;}
while(a.a[a.a[0]]==0&&a.a[0]>1)--a.a[0];R a;}
B O-(C B& a,C B& b){B c=a;c-=b;R c;}
B& O*=(B& a,C B& b){X i,j;if(a==z||b==z){a=z;R a;}
E(buf,0,S(buf));F(i=1;i<=a.a[0];i++)F(j=1;j<=b.a[0];j++)buf[i+j-1]+=(LL)a.a[i]*b.a[j];
buf[0]=a.a[0]+b.a[0]-1;F(i=1;i<=buf[0];++i){buf[i+1]+=buf[i]/e;a.a[i]=buf[i]%e;}
a.a[0]=buf[0];if(buf[buf[0]+1]>0) {a.a[++a.a[0]]=buf[buf[0]+1];}R a;}
B O*(C B& a,C B& b){B c=a;c*=b;R c;}
B O*(C B& a,int x){B c=a;c*=x;R c;}
B& O*=(B& a,int x){if(x==0)    {a=z;R a;}X i;E(buf,0,S(buf));
F(i=1;i<=a.a[0];++i)  buf[i]=(LL)a.a[i]*x;F(i=1;i<=a.a[0];++i)  {a.a[i]=buf[i]%e;buf[i+1]+=buf[i]/e;}
if(buf[a.a[0]+1]>0) {++a.a[0];a.a[a.a[0]]=buf[a.a[0]];}R a;}
B O/(C B& a,C B& b){if(a<b) R z;B t=z,c,d;
c.a[0]=a.a[0]-b.a[0]+1;X i,j;F(i=a.a[0];i>=1;--i){t*=e;t+=a.a[i];F(j=l2b;j>=0;--j)
{d=b*pw22[j];if(t>=d)    {c.a[i]+=pw22[j];t-=d;}}}while(c.a[0]>1&&c.a[c.a[0]]==0) --c.a[0];R c;}
B& O/=(B& a,C B& b){a=a/b;R a;}
B O/(C B& a,int x){B c=a;c/=x;R c;}
B& O/=(B& a,int x){X i;LL t=0;F(i=a.a[0];i>=1;--i)
{t*=e;t+=a.a[i];a.a[i]=t/x;t%=x;}while(a.a[0]>1&&a.a[a.a[0]]==0) --a.a[0];R a;}
B O%(C B& a,C B& b){B t=z,d;X i,j;
F(i=a.a[0];i>=1;--i){t=t*e+a.a[i];F(j=l2b;j>=0;--j){d=b*pw22[j];if(t>=d)t-=d;}}R t;}

B gcd(B a,B b){B c=one,t;while(a!=b){if(a<b) {t=a;a=b;b=t;}if(a.odd()&&b.odd())    a-=b;
else if(a.odd()) b/=2;else if(b.odd())a/=2;else a/=2,b/=2,c*=2;}R a*c;}
B x[3];char str[10010];
int main()
{
    scanf("%s",str+1);x[0]=str+1;
    scanf("%s",str+1);x[1]=str+1;
    (x[0]+x[1]).println();
    if(x[0]>=x[1])
        (x[0]-x[1]).println();
    else
        putchar('-'),(x[1]-x[0]).println();
    (x[0]*x[1]).println();
    (x[0]/x[1]).println();
    (x[0]%x[1]).println();
    R 0;
}
View Code

压行版本:

 1 //#pragma GCC optimize(3)
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long LL;
 8 typedef int B_INT;
 9 #define p_c "%05d"
10 #define i_c "%d"
11 #define b_c "100000"
12 const B_INT p=5,base=100000;
13 const int maxl=4000,l2b=16;
14 struct Bigint{
15 B_INT a[maxl];
16 Bigint(){memset(a,0,sizeof(a));}
17 Bigint(const char *str){*this=str;}
18 Bigint(const Bigint& b){memcpy(a,b.a,sizeof(a));}
19 Bigint(int x){*this=x;}
20 Bigint& operator=(const Bigint& b){memcpy(a,b.a,sizeof(a));return *this;}
21 Bigint& operator=(int x){memset(a,0,sizeof(a));do{a[++a[0]]=x%base;x/=base;}while(x);return *this;}
22 Bigint& operator=(const char *str){memset(a,0,sizeof(a));B_INT k=0,p=1;char *str1=(char*)(str+strlen(str)-1);
23 while(str1>=str){k=k+p*(*str1-48);if(p==base){a[++a[0]]=k%base;k/=base;p=1;}--str1;p*=10;}a[++a[0]]=k;return *this;}
24 void print() const{printf(i_c,a[a[0]]);for(B_INT i=a[0]-1;i>0;i--)printf(p_c,a[i]);}
25 void println() const{print();puts("");}
26 void println(const char* x) const{print();puts(x);}
27 bool odd() const{return a[1]&1;}};
28 LL buf[maxl<<1];const Bigint zero=0,one=1;
29 const B_INT pw22[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
30 bool operator<(const Bigint& a,const Bigint& b){if(a.a[0]!=b.a[0])return a.a[0]<b.a[0];
31 for(B_INT i=a.a[0];i>0;i--)if(a.a[i]!=b.a[i])return a.a[i]<b.a[i];return 0;}
32 bool operator>(const Bigint& a,const Bigint& b){return b<a;}
33 bool operator<=(const Bigint& a,const Bigint& b){return !(b<a);}
34 bool operator>=(const Bigint& a,const Bigint& b){return !(a<b);}
35 bool operator==(const Bigint& a,const Bigint& b){if(a.a[0]!=b.a[0])return 0;
36 for(B_INT i=a.a[0];i>0;--i)if(a.a[i]!=b.a[i])return 0;return 1;}
37 bool operator!=(const Bigint& a,const Bigint& b){return !(a==b);}
38 Bigint& operator+=(Bigint& a,const Bigint& b){B_INT i;a.a[0]=max(a.a[0],b.a[0]);
39 for(i=1;i<=a.a[0];i++){a.a[i]+=b.a[i];a.a[i+1]+=a.a[i]/base;a.a[i]%=base;}if(a.a[a.a[0]+1]>0) a.a[0]++;return a;}
40 Bigint operator+(const Bigint& a,const Bigint& b){Bigint c=a;c+=b;return c;}
41 Bigint operator+(const Bigint& a,int x){Bigint c=a;c+=x;return c;}
42 Bigint& operator+=(Bigint& a,int x){B_INT i;a.a[1]+=x;
43 for(i=1;i<=a.a[0];++i)if(a.a[i]>=base){++a.a[i+1];a.a[i]-=base;}else    break;
44 if(a.a[a.a[0]+1]>0) ++a.a[0];return a;}
45 Bigint& operator-=(Bigint &a,const Bigint &b){B_INT i;a.a[0]=std::max(a.a[0],b.a[0]);
46 for(i=1;i<=a.a[0];++i)a.a[i]-=b.a[i];for(i=1;i<=a.a[0];++i)if(a.a[i]<0){a.a[i]+=base;a.a[i+1]--;}
47 while(a.a[a.a[0]]==0&&a.a[0]>1)--a.a[0];return a;}
48 Bigint operator-(const Bigint& a,const Bigint& b){Bigint c=a;c-=b;return c;}
49 Bigint& operator*=(Bigint& a,const Bigint& b){B_INT i,j;if(a==zero||b==zero){a=zero;return a;}
50 memset(buf,0,sizeof(buf));for(i=1;i<=a.a[0];i++)for(j=1;j<=b.a[0];j++)buf[i+j-1]+=(LL)a.a[i]*b.a[j];
51 buf[0]=a.a[0]+b.a[0]-1;for(i=1;i<=buf[0];++i){buf[i+1]+=buf[i]/base;a.a[i]=buf[i]%base;}
52 a.a[0]=buf[0];if(buf[buf[0]+1]>0) {a.a[++a.a[0]]=buf[buf[0]+1];}return a;}
53 Bigint operator*(const Bigint& a,const Bigint& b){Bigint c=a;c*=b;return c;}
54 Bigint operator*(const Bigint& a,int x){Bigint c=a;c*=x;return c;}
55 Bigint& operator*=(Bigint& a,int x){if(x==0)    {a=zero;return a;}B_INT i;memset(buf,0,sizeof(buf));
56 for(i=1;i<=a.a[0];++i)  buf[i]=(LL)a.a[i]*x;for(i=1;i<=a.a[0];++i)  {a.a[i]=buf[i]%base;buf[i+1]+=buf[i]/base;}
57 if(buf[a.a[0]+1]>0)    {++a.a[0];a.a[a.a[0]]=buf[a.a[0]];}return a;}
58 Bigint operator/(const Bigint& a,const Bigint& b){if(a<b) return zero;Bigint t=zero,c,d;
59 c.a[0]=a.a[0]-b.a[0]+1;B_INT i,j;for(i=a.a[0];i>=1;--i){t*=base;t+=a.a[i];for(j=l2b;j>=0;--j)
60 {d=b*pw22[j];if(t>=d)    {c.a[i]+=pw22[j];t-=d;}}}while(c.a[0]>1&&c.a[c.a[0]]==0) --c.a[0];return c;}
61 Bigint& operator/=(Bigint& a,const Bigint& b){a=a/b;return a;}
62 Bigint operator/(const Bigint& a,int x){Bigint c=a;c/=x;return c;}
63 Bigint& operator/=(Bigint& a,int x){B_INT i;LL t=0;for(i=a.a[0];i>=1;--i)
64 {t*=base;t+=a.a[i];a.a[i]=t/x;t%=x;}while(a.a[0]>1&&a.a[a.a[0]]==0) --a.a[0];return a;}
65 Bigint operator%(const Bigint& a,const Bigint& b){Bigint t=zero,d;B_INT i,j;
66 for(i=a.a[0];i>=1;--i){t=t*base+a.a[i];for(j=l2b;j>=0;--j){d=b*pw22[j];if(t>=d)t-=d;}}return t;}
67 
68 Bigint gcd(Bigint a,Bigint b){Bigint c=one,t;while(a!=b){if(a<b) {t=a;a=b;b=t;}if(a.odd()&&b.odd())    a-=b;
69 else if(a.odd()) b/=2;else if(b.odd())a/=2;else a/=2,b/=2,c*=2;}return a*c;}
70 Bigint x[3];char str[10010];
71 int main()
72 {
73     scanf("%s",str+1);x[0]=str+1;
74     scanf("%s",str+1);x[1]=str+1;
75     (x[0]+x[1]).println();
76     if(x[0]>=x[1])
77         (x[0]-x[1]).println();
78     else
79         putchar('-'),(x[1]-x[0]).println();
80     (x[0]*x[1]).println();
81     (x[0]/x[1]).println();
82     (x[0]%x[1]).println();
83     return 0;
84 }

带注释版本:

  1 //#pragma GCC optimize(3)//O3
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 typedef long long LL;
  8 typedef int B_INT;
  9 #define p_c "%05d"
 10 #define i_c "%d"
 11 #define b_c "100000"
 12 //const char p_c[]="%08lld";
 13 //const char i_c[]="%lld";
 14 //const char b_c[]="100000000";
 15 const B_INT p=5;//压p位,int压4位加乘法可能导致溢出,longlong压8位乘法会炸而且慢
 16 const B_INT base=100000;//压p位,最大数为10^p-1
 17 const int maxl=4000;
 18 //const B_INT l2b=17;//=向上取整(log2(base))
 19 const B_INT l2b=16;//=向下取整(log2(base))
 20 struct Bigint
 21 {
 22 /*
 23 基本类型(char,int,float,double等)的静态成员可以在类里面声明并初始化,
 24 非基本类(char[],string ,自定义等)必须在类里面声明,类外初始化。
 25 */
 26     B_INT a[maxl];//a[0]->len,a[i]->从后往前数第i个p位
 27     Bigint(){memset(a,0,sizeof(a));}
 28     Bigint(const char *str){*this=str;}
 29     Bigint(const Bigint& b){memcpy(a,b.a,sizeof(a));}
 30     Bigint(int x){*this=x;}
 31 
 32     Bigint& operator=(const Bigint& b){memcpy(a,b.a,sizeof(a));return *this;}
 33     Bigint& operator=(int x)
 34     {
 35         memset(a,0,sizeof(a));
 36         do{a[++a[0]]=x%base;x/=base;}while(x);
 37         return *this;
 38     }
 39     Bigint& operator=(const char *str)
 40     {
 41         memset(a,0,sizeof(a));
 42         B_INT k=0,p=1;char *str1=(char*)(str+strlen(str)-1);
 43         while(str1>=str)
 44         {
 45             k=k+p*(*str1-48);
 46             if(p==base){a[++a[0]]=k%base;k/=base;p=1;}
 47             --str1;p*=10;
 48         }
 49         a[++a[0]]=k;
 50         return *this;
 51     }
 52 
 53     friend Bigint operator+(const Bigint&,const Bigint&);
 54     friend Bigint& operator+=(Bigint&,const Bigint&);
 55     friend Bigint operator+(const Bigint&,int x);
 56     friend Bigint& operator+=(Bigint&,int x);
 57 
 58     friend Bigint operator-(const Bigint&,const Bigint&);
 59     friend Bigint& operator-=(Bigint&,const Bigint&);
 60 
 61     friend Bigint operator*(const Bigint&,const Bigint&);
 62     friend Bigint& operator*=(Bigint&,const Bigint&);
 63     friend Bigint operator*(const Bigint&,int x);
 64     friend Bigint& operator*=(Bigint& a,int x);
 65 
 66     friend Bigint operator/(const Bigint&,const Bigint&);
 67     friend Bigint& operator/=(Bigint&,const Bigint&);
 68     friend Bigint operator/(const Bigint& a,int x);
 69     friend Bigint& operator/=(Bigint &,int);
 70 
 71     friend Bigint operator%(const Bigint&,const Bigint&);
 72 
 73     friend bool operator<(const Bigint& a,const Bigint& b);
 74     friend bool operator<=(const Bigint& a,const Bigint& b);
 75     friend bool operator>(const Bigint& a,const Bigint& b);
 76     friend bool operator>=(const Bigint& a,const Bigint& b);
 77     friend bool operator==(const Bigint& a,const Bigint& b);
 78     friend bool operator!=(const Bigint& a,const Bigint& b);
 79 
 80     void print() const
 81     {
 82         printf(i_c,a[a[0]]);
 83         for(B_INT i=a[0]-1;i>0;i--)
 84             printf(p_c,a[i]);
 85     }
 86     void println() const    {print();puts("");}
 87     void println(const char* x) const   {print();puts(x);}
 88     bool odd() const    {return a[1]&1;}
 89 };
 90 LL buf[maxl<<1];
 91 const Bigint zero=0,one=1;
 92 //const Bigint bas=base;
 93 //const Bigint pw2[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
 94 const B_INT pw22[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
 95 bool operator<(const Bigint& a,const Bigint& b)
 96 {
 97     if(a.a[0]!=b.a[0])
 98         return a.a[0]<b.a[0];
 99     for(B_INT i=a.a[0];i>0;i--)
100         if(a.a[i]!=b.a[i])
101             return a.a[i]<b.a[i];
102     return 0;//相等
103 }
104 /*
105 非静态成员函数后面加const(加到非成员函数或静态成员后面会产生编译错误),
106 表示成员函数隐含传入的this指针为 const指针,
107 决定了在该成员函数中,
108 任意修改它所在的类的成员的操作都是不允许的
109 (因为隐含了对this指针的const引用);
110 唯一的例外是对于 mutable修饰的成员。
111 加了const的成员函数可以被非const对象和const对象调用,
112 但不加const的成员函数只能被非const对象调用。
113 下方b是const,const函数不能修改其数据成员
114 */
115 bool operator>(const Bigint& a,const Bigint& b)
116 {
117     return b<a;
118     /*
119     if(a.a[0]!=b.a[0])
120         return a.a[0]>b.a[0];
121     for(int i=a.a[0];i>0;i--)
122         if(a.a[i]!=b.a[i])
123             return a.a[i]>b.a[i];
124     return false;//相等
125     */
126 }
127 bool operator<=(const Bigint& a,const Bigint& b)
128 {
129     return !(b<a);
130     /*
131     if(a.a[0]!=b.a[0])
132         return a.a[0]>b.a[0];
133     for(int i=a.a[0];i>0;i--)
134         if(a.a[i]!=b.a[i])
135             return a.a[i]>b.a[i];
136     return true;//相等
137     */
138 }
139 bool operator>=(const Bigint& a,const Bigint& b)
140 {
141     return !(a<b);
142     /*
143     if(a.a[0]!=b.a[0])
144         return a.a[0]>b.a[0];
145     for(int i=a.a[0];i>0;i--)
146         if(a.a[i]!=b.a[i])
147             return a.a[i]>b.a[i];
148     return true;//相等
149     */
150 }
151 bool operator==(const Bigint& a,const Bigint& b)
152 {
153     if(a.a[0]!=b.a[0])
154         return 0;
155     for(B_INT i=a.a[0];i>0;--i)
156         if(a.a[i]!=b.a[i])
157             return 0;
158     return 1;
159 }
160 bool operator!=(const Bigint& a,const Bigint& b)
161 {
162     return !(a==b);
163 }
164 Bigint operator+(const Bigint& a,const Bigint& b){Bigint c=a;c+=b;return c;}
165 Bigint& operator+=(Bigint& a,const Bigint& b)
166 {
167     B_INT i;
168     a.a[0]=max(a.a[0],b.a[0]);
169     for(i=1;i<=a.a[0];i++)
170     {
171         a.a[i]+=b.a[i];
172         a.a[i+1]+=a.a[i]/base;
173         a.a[i]%=base;
174     }
175     if(a.a[a.a[0]+1]>0) a.a[0]++;
176     return a;
177 }
178 Bigint operator+(const Bigint& a,int x){Bigint c=a;c+=x;return c;}
179 Bigint& operator+=(Bigint& a,int x)//要求不超过base的小数字
180 {
181     B_INT i;
182     a.a[1]+=x;
183     for(i=1;i<=a.a[0];++i)
184         if(a.a[i]>=base)    {++a.a[i+1];a.a[i]-=base;}
185         else    break;
186     if(a.a[a.a[0]+1]>0) ++a.a[0];
187     return a;
188 }
189 Bigint operator-(const Bigint& a,const Bigint& b){Bigint c=a;c-=b;return c;}
190 Bigint& operator-=(Bigint &a,const Bigint &b)//要求保证减数小于被减数
191 {
192     B_INT i;
193     a.a[0]=std::max(a.a[0],b.a[0]);
194     for(i=1;i<=a.a[0];++i)    a.a[i]-=b.a[i];
195     for(i=1;i<=a.a[0];++i)
196         if(a.a[i]<0)    {a.a[i]+=base;a.a[i+1]--;}
197     while(a.a[a.a[0]]==0&&a.a[0]>1)    --a.a[0];
198     return a;
199 }
200 Bigint operator*(const Bigint& a,const Bigint& b){Bigint c=a;c*=b;return c;}
201 Bigint& operator*=(Bigint& a,const Bigint& b)
202 {
203     B_INT i,j;
204     if(a==zero||b==zero)    {a=zero;return a;}
205     memset(buf,0,sizeof(buf));
206     for(i=1;i<=a.a[0];i++)
207         for(j=1;j<=b.a[0];j++)
208             buf[i+j-1]+=(LL)a.a[i]*b.a[j];//注意(LL)
209     buf[0]=a.a[0]+b.a[0]-1;
210     //buf[buf[0]+1]=0
211     for(i=1;i<=buf[0];++i)
212     {
213         buf[i+1]+=buf[i]/base;
214         a.a[i]=buf[i]%base;
215     }
216     a.a[0]=buf[0];
217     if(buf[buf[0]+1]>0) {a.a[++a.a[0]]=buf[buf[0]+1];}
218     return a;
219 }
220 Bigint operator*(const Bigint& a,int x){Bigint c=a;c*=x;return c;}
221 Bigint& operator*=(Bigint& a,int x)//要求不超过base的小数字
222 {
223     if(x==0)    {a=zero;return a;}
224     B_INT i;
225     //a[a[0]+1]=0
226     memset(buf,0,sizeof(buf));
227     for(i=1;i<=a.a[0];++i)
228     {
229         //printf("%d %d\n",i,a.a[i]);
230         buf[i]=(LL)a.a[i]*x;//注意LL
231         //a.a[i+1]+=buf[0]/base;
232         //a.a[i]=buf[i]%base;//printf("%daa\n",a.a[i]);
233     }
234     for(i=1;i<=a.a[0];++i)
235     {
236         //printf("%lldss\n",buf[i]);
237         a.a[i]=buf[i]%base;
238         buf[i+1]+=buf[i]/base;
239     }
240     //if(a.a[a.a[0]+1]>0)    ++a.a[0];
241     //if(buf[buf[0]+1]>0) {a.a[++a.a[0]]=buf[buf[0]+1];}
242     if(buf[a.a[0]+1]>0)    {++a.a[0];a.a[a.a[0]]=buf[a.a[0]];}
243     return a;
244 }
245 Bigint operator/(const Bigint& a,const Bigint& b)
246 {
247     if(a<b) return zero;//必须加这句
248     Bigint t=zero,c,d;c.a[0]=a.a[0]-b.a[0]+1;
249     B_INT i,j;
250     for(i=a.a[0];i>=1;--i)
251     {
252        t*=base;t+=a.a[i];
253        for(j=l2b;j>=0;--j)
254        {
255            d=b*pw22[j];
256            if(t>=d)    {c.a[i]+=pw22[j];t-=d;}
257        }
258        //printf("%dt2\n",c.a[i]);
259     }
260     while(c.a[0]>1&&c.a[c.a[0]]==0) --c.a[0];
261     return c;
262 }
263 Bigint& operator/=(Bigint& a,const Bigint& b){a=a/b;return a;}
264 Bigint operator/(const Bigint& a,int x){Bigint c=a;c/=x;return c;}
265 Bigint& operator/=(Bigint& a,int x)//要求不超过base的小数字
266 {
267     B_INT i;LL t=0;
268     for(i=a.a[0];i>=1;--i)
269     {
270         t*=base;t+=a.a[i];// int xx;printf("%lldkfk\n",t);
271         a.a[i]=t/x;//printf("%dkfk\n",a.a[i]);scanf("%d",&xx);
272         t%=x;
273     }
274     while(a.a[0]>1&&a.a[a.a[0]]==0) --a.a[0];
275     return a;
276 }
277 Bigint operator%(const Bigint& a,const Bigint& b)
278 {
279     //return *this-*this/b*b;
280     Bigint t=zero,d;
281     B_INT i,j;
282     for(i=a.a[0];i>=1;--i)
283     {
284         t=t*base+a.a[i];
285         for(j=l2b;j>=0;--j)
286         {
287             d=b*pw22[j];
288             if(t>=d)    t-=d;
289         }
290     }
291     return t;
292 }
293 
294 Bigint x[3];
295 char str[10010];
296 Bigint gcd(Bigint a,Bigint b)
297 {
298     Bigint c=one,t;
299     while(a!=b)
300     {
301         if(a<b) {t=a;a=b;b=t;}
302         //(a/2).println("k2");
303         //a.print();puts("a");b.print();puts("b");puts("");
304         if(a.odd()&&b.odd())  a-=b;
305         else    if(a.odd())
306             b/=2;
307         else if(b.odd())
308             a/=2;
309         else
310             a/=2,b/=2,c*=2;
311         //a.print();puts("a2");b.print();puts("b2");puts("");c.println("c2");int t;scanf("%d",&t);
312     }
313     return a*c;
314 }
315 //Bigint gcd(Bigint a,Bigint b)
316 //{
317 //    Bigint t;
318 //    static Bigint zero=0;
319 //    while(b!=zero)
320 //    {
321 //        t=a;
322 //        a=b;
323 //        b=t%b;
324 //    }
325 //    return a;
326 //}
327 int main()
328 {
329     //(Bigint("13582583")*15345).print();
330     //(Bigint("3948636459042352478494043859377305164061320248669026579423660")).println();
331     //(Bigint("3948636459042352478494043859377305164061320248669026579423660")/Bigint("2")).println();
332     scanf("%s",str+1);x[0]=str+1;
333     scanf("%s",str+1);x[1]=str+1;
334     //(gcd(x[0],x[1])).print();;
335     (x[0]/x[1]).print();
336     //(x[0]*x[1]).print();
337     //(Bigint("8392523")%Bigint("5")).print();
338     //printf("\n%d",(Bigint("233")-Bigint("233"))==Bigint("1"));
339 //    scanf("%s",str);
340 //    x[0]=str;
341 //    scanf("%s",str);
342 //    x[1]=str;
343 //  if(x[0]<x[1])
344 //  {
345 //      printf("-");
346 //      x[2]=x[0];
347 //      x[0]=x[1];
348 //      x[1]=x[2];
349 //  }
350 //  (x[0]-x[1]).print();
351 //  (x[0]*x[1]).print();
352 //    printf("%d",x[0]>x[1]);
353 //    (x[1]=x[1]).print();
354 //  puts("");
355 //  x[0].print();
356 //  puts("");
357 //  x[1].print();
358     return 0;
359 }
View Code

 (比较)简单的版本:

#include<cstdio>
#include<cstring>
#include<algorithm>
struct Bigint
{
    #define p_c "%08lld"
    #define i_c "%lld"
    typedef long long B_INT;
    static const B_INT p=8;
    static const B_INT base=100000000;
    static const int maxl=3000;
    B_INT a[maxl];
    Bigint()
    {
        memset(a,0,sizeof(a));
    }
    Bigint(const char *str)
    {
        memset(a,0,sizeof(a));
        B_INT k=0,p=1;
        const char *str1=str+strlen(str)-1;
        while(str1>=str)
        {
            k=k+p*(*str1-48);
            if(p==base)
            {
                a[++a[0]]=k%base;
                k/=base;
                p=1;
            }
            str1--;
            p*=10;
        }
        a[++a[0]]=k;
    }
    Bigint(const Bigint& b)
    {
        memcpy(a,b.a,sizeof(a));
    }
    Bigint& operator=(const Bigint& b)
    {
        memcpy(a,b.a,sizeof(a));
        return *this;
    }
    Bigint& operator=(const char *str)
    {
        memset(a,0,sizeof(a));
        B_INT k=0,p=1;
        const char *str1=str+strlen(str)-1;
        while(str1>=str)
        {
            k=k+p*(*str1-48);
            if(p==base)
            {
                a[++a[0]]=k%base;
                k/=base;
                p=1;
            }
            str1--;
            p*=10;
        }
        a[++a[0]]=k;
        return *this;
    }
    Bigint operator+(const Bigint &b) const
    {
        Bigint c;
        B_INT i;
        c.a[0]=std::max(a[0],b.a[0]);
        for(i=1;i<=c.a[0];i++)
        {
            c.a[i]+=a[i]+b.a[i];
            c.a[i+1]=c.a[i]/base;
            c.a[i]%=base;
        }
        if(c.a[c.a[0]+1]>0)
            c.a[0]++;
        return c;
    }
    Bigint operator*(const Bigint &b) const
    {
        Bigint c;
        B_INT i,j;
        for(i=1;i<=a[0];i++)
            for(j=1;j<=b.a[0];j++)
                c.a[i+j-1]+=a[i]*b.a[j];
        c.a[0]=a[0]+b.a[0]-1;
        for(i=1;i<=c.a[0];i++)
        {
            c.a[i+1]+=c.a[i]/base;
            c.a[i]%=base;
        }
        if(c.a[c.a[0]+1]>0)
            c.a[0]++;
        return c;
    }
    Bigint operator-(const Bigint &b) const
    {
        Bigint c;
        B_INT i;
        c.a[0]=std::max(a[0],b.a[0]);
        for(i=1;i<=c.a[0];i++)
            c.a[i]=a[i]-b.a[i];
        for(i=1;i<=c.a[0];i++)
            if(c.a[i]<0)
            {
                c.a[i]+=base;
                c.a[i+1]--;
            }
        while(c.a[c.a[0]]==0&&c.a[0]>0)
            c.a[0]--;
        return c;
    }
    Bigint& operator+=(const Bigint &b)
    {
        *this=*this+b;
        return *this;
    }
    Bigint& operator-=(const Bigint &b)
    {
        *this=*this-b;
        return *this;
    }
    Bigint& operator*=(const Bigint &b)
    {
        *this=(*this)*b;
        return *this;
    }
    bool operator<(const Bigint &b) const
    {
        if(a[0]!=b.a[0])
            return a[0]<b.a[0];
        for(B_INT i=a[0];i>0;i--)
            if(a[i]!=b.a[i])
                return a[i]<b.a[i];
        return false;
    }
    bool operator>(const Bigint &b) const
    {
        return b<*this;
    }
    bool operator<=(const Bigint &b) const
    {
        return !(b<*this);
    }
    bool operator>=(const Bigint &b) const
    {
        return !(*this<b);
    }
    bool operator==(const Bigint &b) const
    {
        if(a[0]!=b.a[0])
            return false;
        for(B_INT i=a[0];i>0;i--)
            if(a[i]!=b.a[i])
                return false;
        return true;
    }
    bool operator!=(const Bigint &b) const
    {
        return !(*this==b);
    }
    void print()
    {
        printf(i_c,a[a[0]]);
        for(B_INT i=a[0]-1;i>0;i--)
            printf(p_c,a[i]);
    }
    #undef p_c
    #undef i_c
};
int main()
{
    return 0;
}

带说明版本:

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 typedef long long B_INT;
  5 const char p_c[]="%08lld";
  6 const char i_c[]="%lld";
  7 struct Bigint
  8 {
  9 /*
 10 基本类型(char,int,float,double等)的静态成员可以在类里面声明并初始化,
 11 非基本类(char[],string ,自定义等)必须在类里面声明,类外初始化。
 12 */
 13     static const B_INT p=8;//压p位,int压4位加乘法可能导致溢出
 14     static const B_INT base=100000000;//压p位,最大数为10^p-1
 15     static const int maxl=3000;
 16     B_INT a[maxl];//a[0]->len,a[i]->从后往前数第i个p位
 17     Bigint()
 18     {
 19         memset(a,0,sizeof(a));
 20     }
 21 //  Bigint(char *str)
 22 //  {
 23 //      memset(a,0,sizeof(a));
 24 //      B_INT k=0,p=1;
 25 //      char *str1=str+strlen(str)-1;
 26 //      while(str1>=str)
 27 //      {
 28 //          k=k+p*(*str1-48);
 29 //          if(p==base)
 30 //          {
 31 //              a[++a[0]]=k%base;
 32 //              k/=base;
 33 //              p=1;
 34 //          }
 35 //          str1--;
 36 //          p*=10;
 37 //      }
 38 //      a[++a[0]]=k;
 39 //  }
 40     Bigint(const Bigint& b)
 41     {
 42         memcpy(a,b.a,sizeof(a));
 43     }
 44     Bigint& operator=(const Bigint& b)
 45     {
 46         memcpy(a,b.a,sizeof(a));
 47         return *this;
 48     }
 49     Bigint& operator=(char *str)
 50     {
 51         memset(a,0,sizeof(a));
 52         B_INT k=0,p=1;
 53         char *str1=str+strlen(str)-1;
 54         while(str1>=str)
 55         {
 56             k=k+p*(*str1-48);
 57             if(p==base)
 58             {
 59                 a[++a[0]]=k%base;
 60                 k/=base;
 61                 p=1;
 62             }
 63             str1--;
 64             p*=10;
 65         }
 66         a[++a[0]]=k;
 67         return *this;
 68     }
 69     Bigint operator+(const Bigint &b) const
 70     {
 71         Bigint c;
 72         B_INT i;
 73         c.a[0]=std::max(a[0],b.a[0]);
 74         for(i=1;i<=c.a[0];i++)
 75         {
 76             c.a[i]+=a[i]+b.a[i];
 77             c.a[i+1]=c.a[i]/base;
 78             c.a[i]%=base;
 79         }
 80         if(c.a[c.a[0]+1]>0)
 81             c.a[0]++;
 82         return c;
 83     }
 84     Bigint operator*(const Bigint &b) const
 85     {
 86         Bigint c;
 87         B_INT i,j;
 88         for(i=1;i<=a[0];i++)
 89             for(j=1;j<=b.a[0];j++)
 90                 c.a[i+j-1]+=a[i]*b.a[j];
 91         c.a[0]=a[0]+b.a[0]-1;
 92         for(i=1;i<=c.a[0];i++)
 93         {
 94             c.a[i+1]+=c.a[i]/base;
 95             c.a[i]%=base;
 96         }
 97         if(c.a[c.a[0]+1]>0)
 98             c.a[0]++;
 99         return c;
100     }
101     Bigint operator-(const Bigint &b) const//要求保证减数小于被减数
102     {
103         Bigint c;
104         B_INT i;
105         c.a[0]=std::max(a[0],b.a[0]);
106         for(i=1;i<=c.a[0];i++)
107             c.a[i]=a[i]-b.a[i];
108         for(i=1;i<=c.a[0];i++)
109             if(c.a[i]<0)
110             {
111                 c.a[i]+=base;
112                 c.a[i+1]--;
113             }
114         while(c.a[c.a[0]]==0&&c.a[0]>0)
115             c.a[0]--;
116         return c;
117     }
118     Bigint& operator+=(const Bigint &b)
119     {
120         *this=*this+b;
121         return *this;
122     }
123     Bigint& operator-=(const Bigint &b)
124     {
125         *this=*this-b;
126         return *this;
127     }
128     Bigint& operator*=(const Bigint &b)
129     {
130         *this=(*this)*b;
131         return *this;
132     }
133     bool operator<(const Bigint &b) const
134     {
135         if(a[0]!=b.a[0])
136             return a[0]<b.a[0];
137         for(B_INT i=a[0];i>0;i--)
138             if(a[i]!=b.a[i])
139                 return a[i]<b.a[i];
140         return false;//相等
141     }
142     /*
143     非静态成员函数后面加const(加到非成员函数或静态成员后面会产生编译错误),
144     表示成员函数隐含传入的this指针为 const指针,
145     决定了在该成员函数中,
146     任意修改它所在的类的成员的操作都是不允许的
147     (因为隐含了对this指针的const引用);
148     唯一的例外是对于 mutable修饰的成员。
149     加了const的成员函数可以被非const对象和const对象调用,
150     但不加const的成员函数只能被非const对象调用。
151     下方b是const,const函数不能修改其数据成员
152     */
153     bool operator>(const Bigint &b) const
154     {
155         return b<*this;
156         /*
157         if(a[0]!=b.a[0])
158             return a[0]>b.a[0];
159         for(int i=a[0];i>0;i--)
160             if(a[i]!=b.a[i])
161                 return a[i]>b.a[i];
162         return false;//相等
163         */
164     }
165     bool operator<=(const Bigint &b) const
166     {
167         return !(b<*this);
168         /*
169         if(a[0]!=b.a[0])
170             return a[0]>b.a[0];
171         for(int i=a[0];i>0;i--)
172             if(a[i]!=b.a[i])
173                 return a[i]>b.a[i];
174         return true;//相等
175         */
176     }
177     bool operator>=(const Bigint &b) const
178     {
179         return !(*this<b);
180         /*
181         if(a[0]!=b.a[0])
182             return a[0]>b.a[0];
183         for(int i=a[0];i>0;i--)
184             if(a[i]!=b.a[i])
185                 return a[i]>b.a[i];
186         return true;//相等
187         */
188     }
189     bool operator==(const Bigint &b) const
190     {
191         if(a[0]!=b.a[0])
192             return false;
193         for(B_INT i=a[0];i>0;i--)
194             if(a[i]!=b.a[i])
195                 return false;
196         return true;
197     }
198     bool operator!=(const Bigint &b) const
199     {
200         return !(*this==b);
201     }
202     void print()
203     {
204         printf(i_c,a[a[0]]);
205         for(B_INT i=a[0]-1;i>0;i--)
206             printf(p_c,a[i]);
207     }
208 }x[3];
209 char str[10010];
210 int main()
211 {
212     scanf("%s",str);
213     x[0]=str;
214     scanf("%s",str);
215     x[1]=str;
216 //  if(x[0]<x[1])
217 //  {
218 //      printf("-");
219 //      x[2]=x[0];
220 //      x[0]=x[1];
221 //      x[1]=x[2];
222 //  }
223 //  (x[0]-x[1]).print();
224 //  (x[0]*x[1]).print();
225     //printf("%d",x[0]>x[1]);
226     (x[1]=x[1]).print();
227 //  puts("");
228 //  x[0].print();
229 //  puts("");
230 //  x[1].print();
231     return 0;
232 }

old2:

#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long B_INT;
const char p_c[]="%08lld";
const char i_c[]="%lld";
struct Bigint
{
/*
基本类型(char,int,float,double等)的静态成员可以在类里面声明并初始化,
非基本类(char[],string ,自定义等)必须在类里面声明,类外初始化。
*/
	static const B_INT p=8;//压p位,int压4位加乘法可能导致溢出
	static const B_INT base=100000000;//压p位,最大数为10^p-1
	static const int maxl=3000;
	B_INT a[maxl];//a[0]->len,a[i]->从后往前数第i个p位
	Bigint()
	{
		memset(a,0,sizeof(a));
	}
//	Bigint(char *str)
//	{
//		memset(a,0,sizeof(a));
//		B_INT k=0,p=1;
//		char *str1=str+strlen(str)-1;
//		while(str1>=str)
//		{
//			k=k+p*(*str1-48);
//			if(p==base)
//			{
//				a[++a[0]]=k%base;
//				k/=base;
//				p=1;
//			}
//			str1--;
//			p*=10;
//		}
//		a[++a[0]]=k;
//	}
	Bigint(const Bigint& b)
	{
		memcpy(a,b.a,sizeof(a));
	}
	Bigint& operator=(const Bigint& b)
	{
		memcpy(a,b.a,sizeof(a));
	}
	Bigint& operator=(char *str)
	{
		memset(a,0,sizeof(a));
		B_INT k=0,p=1;
		char *str1=str+strlen(str)-1;
		while(str1>=str)
		{
			k=k+p*(*str1-48);
			if(p==base)
			{
				a[++a[0]]=k%base;
				k/=base;
				p=1;
			}
			str1--;
			p*=10;
		}
		a[++a[0]]=k;
		return *this;
	}
	Bigint operator+(const Bigint &b) const
	{
		Bigint c;
		B_INT i;
		c.a[0]=std::max(a[0],b.a[0]);
		for(i=1;i<=c.a[0];i++)
		{
			c.a[i]+=a[i]+b.a[i];
			c.a[i+1]=c.a[i]/base;
			c.a[i]%=base;
		}
		if(c.a[c.a[0]+1]>0)
			c.a[0]++;
		return c;
	}
	Bigint operator*(const Bigint &b) const
	{
		Bigint c;
		B_INT i,j;
		for(i=1;i<=a[0];i++)
			for(j=1;j<=b.a[0];j++)
				c.a[i+j-1]+=a[i]*b.a[j];
		c.a[0]=a[0]+b.a[0]-1;
		for(i=1;i<=c.a[0];i++)
		{
			c.a[i+1]+=c.a[i]/base;
			c.a[i]%=base;
		}
		if(c.a[c.a[0]+1]>0)
			c.a[0]++;
		return c;
	}
	Bigint operator-(const Bigint &b) const//要求保证减数小于被减数 
	{
		Bigint c;
		B_INT i;
		c.a[0]=std::max(a[0],b.a[0]);
		for(i=1;i<=c.a[0];i++)
			c.a[i]=a[i]-b.a[i];
		for(i=1;i<=c.a[0];i++)
			if(c.a[i]<0)
			{
				c.a[i]+=base;
				c.a[i+1]--;
			}
		while(c.a[c.a[0]]==0&&c.a[0]>0)
			c.a[0]--;
		return c;
	}
	Bigint& operator+=(const Bigint &b)
	{
		*this=*this+b;
		return *this;
	}
	Bigint& operator-=(const Bigint &b)
	{
		*this=*this-b;
		return *this;
	}
	Bigint& operator*=(const Bigint &b)
	{
		*this=(*this)*b;
		return *this;
	}
	bool operator<(const Bigint &b) const
	{
		if(a[0]!=b.a[0])
			return a[0]<b.a[0];
		for(B_INT i=a[0];i>0;i--)
			if(a[i]!=b.a[i])
				return a[i]<b.a[i];
		return false;//相等
	}
	/*
	非静态成员函数后面加const(加到非成员函数或静态成员后面会产生编译错误),
	表示成员函数隐含传入的this指针为 const指针,
	决定了在该成员函数中,
	任意修改它所在的类的成员的操作都是不允许的
	(因为隐含了对this指针的const引用);
	唯一的例外是对于 mutable修饰的成员。
	加了const的成员函数可以被非const对象和const对象调用,
	但不加const的成员函数只能被非const对象调用。
	下方b是const,const函数不能修改其数据成员
	*/
	bool operator>(const Bigint &b) const
	{
		return b<*this;
		/*
		if(a[0]!=b.a[0])
			return a[0]>b.a[0];
		for(int i=a[0];i>0;i--)
			if(a[i]!=b.a[i])
				return a[i]>b.a[i];
		return false;//相等
		*/
	}
	bool operator<=(const Bigint &b) const
	{
		return !(b<*this);
		/*
		if(a[0]!=b.a[0])
			return a[0]>b.a[0];
		for(int i=a[0];i>0;i--)
			if(a[i]!=b.a[i])
				return a[i]>b.a[i];
		return true;//相等
		*/
	}
	bool operator>=(const Bigint &b) const
	{
		return !(*this<b);
		/*
		if(a[0]!=b.a[0])
			return a[0]>b.a[0];
		for(int i=a[0];i>0;i--)
			if(a[i]!=b.a[i])
				return a[i]>b.a[i];
		return true;//相等
		*/
	}
	bool operator==(const Bigint &b) const
	{
		if(a[0]!=b.a[0])
			return false;
		for(B_INT i=a[0];i>0;i--)
			if(a[i]!=b.a[i])
				return false;
		return true;
	}
	bool operator!=(const Bigint &b) const
	{
		return !(*this==b);
	}
	void print()
	{
		printf(i_c,a[a[0]]);
		for(B_INT i=a[0]-1;i>0;i--)
			printf(p_c,a[i]);
	}
}x[3];
char str[10010];
int main()
{
	scanf("%s",str);
	x[0]=str;
	scanf("%s",str);
	x[1]=str;
//	if(x[0]<x[1])
//	{
//		printf("-");
//		x[2]=x[0];
//		x[0]=x[1];
//		x[1]=x[2];
//	}
//	(x[0]-x[1]).print();
//	(x[0]*x[1]).print();
	//printf("%d",x[0]>x[1]);
	(x[1]=x[1]).print();
//	puts("");
//	x[0].print();
//	puts("");
//	x[1].print();
	return 0;
}

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:生理周期POJ 1006

下一篇:C语言中的库函数memcpy、memmove、memset、memchr、memcmp