（维护）高精模板（缺除法）
2018-06-27 10:02:08来源：未知 阅读 ()
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 }
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 }
压行版本：
#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; }
奇怪的东西：
//#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; }
压行版本：
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 }
（比较）简单的版本：
#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
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
相关文章
- C++冒泡排序 （基于函数模板实现） 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
热门词条
最新资讯
热门关注
热门标签