1 namespace BigNumber{ 2 const int L=5010,Base=10000,Bit=4; 3 const LL MaxInt=2147483647; 4 const int Pw10[15]={ 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; 5 const int Pw2[20]={ 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536}; 6 7 LL DOF[L]; 8 9 struct BigNum{ 10 int v[L],le,flag; 11 BigNum(){ 12 memset(v,0,sizeof v); le=flag=1; 13 } 14 BigNum(int x){ 15 flag=1; le=1; memset(v,0,sizeof v); 16 if (x<0) flag=-1,x=-x; 17 v[1]=x; 18 while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le; 19 } 20 BigNum(LL x){ 21 flag=1; le=1; memset(v,0,sizeof v); 22 if (x<0) flag=-1,x=-x; 23 v[1]=x%Base; v[2]=x/Base%Base; 24 v[3]=x/Base/Base%Base; v[4]=x/Base/Base/Base; 25 le=4; 26 while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le; 27 while (v[le]==0 && le>1) --le; 28 } 29 BigNum(int len,int fir){ 30 memset(v,0,sizeof v); 31 le=len; v[le]=fir; flag=1; 32 } 33 BigNum(const BigNum &a,int x){ 34 memset(v,0,sizeof v); 35 le=a.le+x; flag=a.flag; 36 for (int i=1;i<=a.le;++i) v[i+x]=a.v[i]; 37 } 38 int IntoInt(){ 39 if (le>3) cerr <<"Error: cannot change so big into int!"< =1;--i) d=d*Base+v[i]; 42 if (flag==-1) d=-d; 43 if (d>MaxInt || -d 63 bool operator ==(const BigNum &a)const{ 64 if (le!=a.le || flag!=a.flag) return 0; 65 for (int i=1;i<=le;++i) if (v[i]!=a.v[i]) return 0; 66 return 1; 67 } 68 bool operator <(const BigNum &a)const{ 69 if (flag < a.flag) return 1; 70 if (flag > a.flag) return 0; 71 if (le < a.le) return flag == 1 ? 1 : 0; 72 if (le > a.le) return flag == 1 ? 0 : 1; 73 for (int i=le;i>=1;--i){ 74 if (v[i] a.v[i]) return flag==1? 0:1; 76 }return 0; 77 } 78 bool operator >(const BigNum &a)const{ 79 if (flag < a.flag) return 0; 80 if (flag > a.flag) return 1; 81 if (le < a.le) return flag == 1 ? 0 : 1; 82 if (le > a.le) return flag == 1 ? 1 : 0; 83 for (int i=le;i>=1;--i){ 84 if (v[i] a.v[i]) return flag==1? 1:0; 86 }return 0; 87 } 88 bool operator ==(const int &x)const{ 89 return *this == BigNum(x); 90 } 91 92 93 //Add and Sub --> 94 void operator +=(const BigNum &x){ 95 BigNum a=*this; BigNum b=x; memset(v,0,sizeof v); 96 flag=1; 97 if (a.flag==-1 && b.flag==-1){ 98 flag=-1; a.flag=1; b.flag=1; 99 }100 if (a < b) swap(a,b);101 if (b.flag==-1){102 b.flag=1;103 if (a < b) swap(a,b),flag=-1;104 b.flag=-1;105 }106 if (b.flag==1){107 le=a.le;108 for (int i=1;i<=le;++i) v[i]=a.v[i]+b.v[i];109 for (int i=1;i<=le;++i) v[i+1]+=v[i]/Base,v[i]%=Base;110 while (v[le+1]>0) ++le;111 }else{112 le=a.le;113 for (int i=1;i<=le;++i) v[i]=a.v[i]-b.v[i];114 for (int i=1;i<=le;++i) if (v[i]<0) --v[i+1],v[i]+=Base;115 while (v[le]==0 && le>1) --le;116 }117 }118 void operator +=(int x){119 *this += BigNum(x);120 }121 void operator -=(const BigNum &x){122 BigNum a=x; a.flag=-a.flag;123 *this += a;124 }125 void operator -=(int x){126 *this -= BigNum(x);127 }128 129 130 BigNum &operator ++(){131 return *this += 1, *this;132 }133 BigNum &operator --(){134 return *this -= 1, *this;135 }136 BigNum operator ++(int){137 BigNum c(*this);138 ++ *this; return c;139 }140 BigNum operator --(int){141 BigNum c(*this);142 -- *this; return c;143 }144 145 146 //Mul -->147 void operator *=(const BigNum &x){148 BigNum a=x;149 if (flag==a.flag) flag=1;else flag=-1;150 a.flag=1;151 152 memset(DOF,0,sizeof DOF);153 for (int i=1;i<=le;++i)154 for (int j=1;j<=a.le;++j)155 DOF[i+j-1]+=v[i]*a.v[j];156 le+=a.le+9;157 for (int i=1; i<=le; ++i) v[i]=0;158 for (int i=1;i<=le;++i) DOF[i+1]+=DOF[i]/Base,DOF[i]%=Base;159 while (DOF[le]==0 && le>1) --le;160 for (int i=1;i<=le;++i) v[i]=DOF[i];161 }162 void operator *=(const int &x){163 *this *= BigNum(x);164 }165 void operator *=(const LL &x){166 *this *= BigNum(x);167 }168 169 170 //Div -->171 void operator /=(int x){172 if (x==0){173 cerr <<"Error: div 0!"; return;174 }175 BigNum a; a=x;176 if (flag==a.flag) flag=1;else flag=-1;177 a.flag=1;178 if (x < 0) x = -x;179 180 memset(DOF,0,sizeof DOF);181 LL rest=0;182 for (int i=le;i>=1;--i){183 rest=rest*Base+v[i];184 DOF[i]=rest/x; rest%=x;185 v[i]=0;186 }187 for (int i=le;i>=1;--i) v[i]=DOF[i];188 while (v[le]==0 && le>1) --le;189 }190 void operator /=(const BigNum &x){191 if (x==0){192 cerr <<"Error: div 0!"; return;193 }194 BigNum a=*this,b=x,c,d;195 if (a.flag==b.flag) flag=1;else flag=-1;196 a.flag = b.flag = 1;197 for (int i=le;i>0;--i) v[i]=0;198 le=a.le-b.le+1;199 200 for (int i=le;i>=1;--i){201 c=BigNum(b,i-1);202 for (int j=log2(Base);j>=0;--j){203 d=c; d*=Pw2[j];204 if (!(a < d)) v[i]+=Pw2[j],a-=d;205 }206 }207 for (int i=1;i<=le;++i) v[i+1]+=v[i]/Base,v[i]%=Base;208 while (v[le+1]>0) ++le;209 while (v[le]==0 && le>1) --le;210 }211 212 213 //Mod -->214 void operator %=(int p){215 if (p==0){216 cerr <<"Error: mod 0!"; return;217 }218 LL d=0; if (p < 0) p=-p;219 for (int i=le;i>=1;--i) d=(d*Base+v[i])%p,v[i]=0;220 le=1; v[1]=d;221 while (v[le]>=Base) v[le+1]+=v[le]/Base,v[le]%=Base,++le;222 }223 224 void operator %=(const BigNum &x){225 if (x==0){226 cerr <<"Error: mod 0!"; return;227 }228 BigNum a=*this,b=x,c,d;229 for (int i=le;i>0;--i) v[i]=0;230 le=a.le-b.le+1;231 232 for (int i=le;i>=1;--i){233 c=BigNum(b,i-1);234 for (int j=log2(Base);j>=0;--j){235 d=c; d*=Pw2[j];236 if (!(a < d)) a-=d;237 }238 }239 *this = a;240 }241 242 243 //Power -->244 BigNum pow(int b){245 BigNum a,c; a=*this; c=1;246 for (;b;b>>=1,a*=a) if (b&1) c*=a;247 return c;248 }249 BigNum pow(int x,int b){250 BigNum c,a; c=1; a=x;251 for (;b;b>>=1,a*=a) if (b&1) c*=a;252 return c;253 }254 int pow2(int a,int b){255 int c=1;256 for (;b;b>>=1,a*=a) if (b&1) c*=a;257 return c;258 }259 260 261 //Shr and Shl -->262 void operator <<=(int x){263 if (x<=30) *this *= pow2(2,x);264 else *this *= pow(2,x);265 }266 void operator >>=(int x){267 if (x<=30) *this /= pow2(2,x);268 else *this /= pow(2,x);269 }270 271 272 void rev() {273 if (le > 1 || v[le]) flag = -flag;274 return;275 }276 277 };278 279 280 //Compare -->281 bool operator ==(const int &a,const BigNum &b){282 return b == a;283 }284 bool operator !=(const BigNum &a,const BigNum &b){285 return !(a == b);286 }287 bool operator !=(const BigNum &a,const int &b){288 return !(a == b);289 }290 bool operator !=(const int &a,const BigNum &b){291 return !(b == a);292 }293 294 295 bool operator <(const BigNum &a,const int &b){296 return a < BigNum(b);297 }298 bool operator <(const int &a,const BigNum &b){299 return BigNum(a) < b;300 }301 bool operator >(const BigNum &a,const int &b){302 return a > BigNum(b);303 }304 bool operator >(const int &a,const BigNum &b){305 return BigNum(a) > b;306 }307 bool operator <=(const BigNum &a,const BigNum &b){308 if (a > b) return 0; return 1;309 }310 bool operator >=(const BigNum &a,const BigNum &b){311 if (a < b) return 0; return 1;312 }313 bool operator <=(const BigNum &a,const int &b){314 if (a > b) return 0; return 1;315 }316 bool operator <=(const int &a,const BigNum &b){317 if (a > b) return 0; return 1;318 }319 bool operator >=(const BigNum &a,const int &b){320 if (a < b) return 0; return 1;321 }322 bool operator >=(const int &a,const BigNum &b){323 if (a < b) return 0; return 1;324 }325 326 327 int max(const int &a,const int &b){328 if (a < b) return b; return a;329 }330 int min(const int &a,const int &b){331 if (a < b) return a; return b;332 }333 BigNum max(const BigNum &a,const BigNum &b){334 if (a < b) return b; return a;335 }336 BigNum min(const BigNum &a,const BigNum &b){337 if (a < b) return a; return b;338 }339 340 341 //Add -->342 BigNum operator +(const BigNum &a,const BigNum &b){343 BigNum c=a; c+=b; return c;344 }345 BigNum operator +(const BigNum &a,const int &b){346 BigNum c=a; c+=b; return c;347 }348 BigNum operator +(const int &a,const BigNum &b){349 BigNum c=b; c+=a; return c;350 }351 352 353 //Sub -->354 BigNum operator -(const BigNum &a,const BigNum &b){355 BigNum c=a; c-=b; return c;356 }357 BigNum operator -(const BigNum &a,const int &b){358 BigNum c=a; c-=b; return c;359 }360 BigNum operator -(const int &a,const BigNum &b){361 BigNum c=b; c-=a; return c;362 }363 364 365 //Mul -->366 BigNum operator *(const BigNum &a,const BigNum &b){367 BigNum c=a; c*=b; return c;368 }369 BigNum operator *(const BigNum &a,const int &b){370 BigNum c=a; c*=b; return c;371 }372 BigNum operator *(const int &a,const BigNum &b){373 BigNum c=b; c*=a; return c;374 }375 376 377 //Div -->378 BigNum operator /(const BigNum &a,const int &b){379 BigNum c=a; c/=b; return c;380 }381 BigNum operator /(const int &a,const BigNum &b){382 BigNum c=b; c/=a; return c;383 }384 BigNum operator /(const BigNum &a,const BigNum &b){385 BigNum c=a; c/=b; return c;386 }387 388 389 //Mod -->390 BigNum operator %(const BigNum &a,const int &b){391 BigNum c=a; c%=b; return c;392 }393 BigNum operator %(const int &a,const BigNum &b){394 BigNum c=b; c%=a; return c;395 }396 BigNum operator %(const BigNum &a,const BigNum &b){397 BigNum c=a; c%=b; return c;398 }399 400 //Shr and Shl -->401 BigNum operator <<(const BigNum &a,const int b){402 BigNum c=a; c<<=b; return c;403 }404 BigNum operator <<(const BigNum &a,BigNum &b){405 return a << b.IntoInt();406 }407 BigNum operator >>(const BigNum &a,const int &b){408 BigNum c=a; c>>=b; return c;409 }410 BigNum operator >>(const BigNum &a,BigNum &b){411 return a >> b.IntoInt();412 }413 414 415 //Abs -->416 BigNum abs(const BigNum &x){417 BigNum c=x; c.flag=1; return c;418 }419 420 421 //Odd -->422 int odd(const BigNum &x){423 if (x.v[1] & 1) return 1; return 0;424 }425 426 427 //Gcd -->428 BigNum gcd(const BigNum &x,const BigNum &y){429 if (x.le == 1 && !x.v[1]) return y;430 if (y.le == 1 && !y.v[1]) return x;431 BigNum a=x,b=y,c=BigNum(1);432 while (a!=b){433 if (a < b) swap(a,b);434 if (odd(a) && odd(b)) a-=b; else435 if (odd(a)) b/=2; else436 if (odd(b)) a/=2; else437 a/=2,b/=2,c*=2;438 }return a*c;439 }440 441 442 //Sqrt -->443 BigNum sqrt(const BigNum &x){444 if (x<0){445 cerr <<"Error: sqrt nagetive!";446 return 0;447 }448 BigNum l,r,m,A;449 l=BigNum(x.le/2,1); r=BigNum(x.le/2+2,1);450 while (l<=r){451 m=(l+r)>>1;452 if (m*m<=x) A=m,l=m+1; else r=m-1;453 }return A;454 }455 BigNum sqrt(const BigNum &a,int b){456 BigNum x=a;457 if (x<0 && b%2==0){458 cerr <<"Error: sqrt nagetive!";459 return 0;460 }461 BigNum l,r,m,A;462 int frog=x.flag; x.flag=1;463 l=0; r=1;464 while (r.pow(b) >1;467 if (m.pow(b)<=x) A=m,l=m+1; else r=m-1;468 }469 if (frog==-1) A.flag=-1;470 return A;471 }472 473 474 //Read and Print -->475 string yz; char cyz;476 void Read(BigNum &a){477 a.Clear();478 while (cin.peek()==' ') getchar();479 if (cin.peek()=='-'){480 a.flag=-1; cin >>cyz;481 }482 cin >>yz;483 int len=yz.length();484 a.le=len/Bit;485 for (int i=1;i<=a.le;++i){486 int l=len-Bit*i,r=l+Bit-1;487 for (int j=l;j<=r;++j) a.v[i]=a.v[i]*10+yz[j]-'0';488 }489 if(len%Bit!=0){490 int r=len-Bit*a.le-1;491 ++a.le;492 for (int j=0;j<=r;++j) a.v[a.le]=a.v[a.le]*10+yz[j]-'0';493 }494 }495 496 void PrintWith(int x,int k){497 for (int i=k-1;i>=0;--i) if (Pw10[i]>x) putchar('0');498 else putchar(x/Pw10[i]+'0'),x%=Pw10[i];499 }500 void Print(const BigNum &a){501 if (a.flag==-1 && (a.le > 1 || a.v[a.le])) putchar('-');502 printf("%d",a.v[a.le]);503 for (int i=a.le-1;i>=1;--i) PrintWith(a.v[i],Bit);504 }505 void Println(const BigNum &a){506 Print(a); puts("");507 }508 };509 510 using namespace BigNumber;