00001
00002 #ifndef _Integer_h
00003 #define _Integer_h
00004
00005
00006 #include <iostream>
00007
00008 using namespace std;
00009
00010
00011 struct IntRep
00012 {
00013 IntRep( ) { }
00014 IntRep( unsigned short l, unsigned short s1, short s2, unsigned short s3 ) : len( l ), sz( s1 ), sgn( s2 ) { s[0] = s3; }
00015
00016 unsigned short len;
00017 unsigned short sz;
00018 short sgn;
00019 unsigned short s[1];
00020 };
00021
00022
00023
00024
00025 #define STATIC_IntRep(rep) ((rep)->sz==0)
00026
00027 IntRep* Ialloc(IntRep*, const unsigned short *, int, int, int);
00028 IntRep* Icalloc(IntRep*, int);
00029 IntRep* Icopy_ulong(IntRep*, unsigned long);
00030 IntRep* Icopy_long(IntRep*, long);
00031 IntRep* Icopy(IntRep*, const IntRep*);
00032 IntRep* Iresize(IntRep*, int);
00033 IntRep* add(const IntRep*, int, const IntRep*, int, IntRep*);
00034 IntRep* add(const IntRep*, int, long, IntRep*);
00035 IntRep* multiply(const IntRep*, const IntRep*, IntRep*);
00036 IntRep* multiply(const IntRep*, long, IntRep*);
00037 IntRep* lshift(const IntRep*, long, IntRep*);
00038 IntRep* lshift(const IntRep*, const IntRep*, int, IntRep*);
00039 IntRep* bitop(const IntRep*, const IntRep*, IntRep*, char);
00040 IntRep* bitop(const IntRep*, long, IntRep*, char);
00041 IntRep* power(const IntRep*, long, IntRep*);
00042 IntRep* div(const IntRep*, const IntRep*, IntRep*);
00043 IntRep* mod(const IntRep*, const IntRep*, IntRep*);
00044 IntRep* div(const IntRep*, long, IntRep*);
00045 IntRep* mod(const IntRep*, long, IntRep*);
00046 IntRep* _compl(const IntRep*, IntRep*);
00047 IntRep* abs(const IntRep*, IntRep*);
00048 IntRep* negate1(const IntRep*, IntRep*);
00049 IntRep* pow(const IntRep*, long);
00050 IntRep* gcd(const IntRep*, const IntRep* y);
00051 int compare(const IntRep*, const IntRep*);
00052 int compare(const IntRep*, long);
00053 int ucompare(const IntRep*, const IntRep*);
00054 int ucompare(const IntRep*, long);
00055 char* Itoa(const IntRep* x, int base = 10, int width = 0);
00056 char* cvtItoa(const IntRep* x, char* fmt, int& fmtlen, int base,
00057 int showbase, int width, int align_right,
00058 char fillchar, char Xcase, int showpos);
00059 IntRep* atoIntRep(const char* s, int base = 10);
00060 long Itolong(const IntRep*);
00061 int Iislong(const IntRep*);
00062 long lg(const IntRep*);
00063
00064
00065
00066 static struct ZeroRep : public IntRep
00067 {
00068 public:
00069 ZeroRep( ) : IntRep( 1, 0, 1, 0 ) { }
00070
00071
00072 } _ZeroRep;
00073
00074
00075 static struct OneRep : public IntRep
00076 {
00077 public:
00078 OneRep( ) : IntRep( 1, 0, 1, 1 ) { }
00079
00080 } _OneRep;
00081
00082 static struct MinusOneRep : public IntRep
00083 {
00084 public:
00085 MinusOneRep( ) : IntRep( 1, 0, 0, 1 ) { }
00086
00087 } _MinusOneRep;
00088
00089
00090 IntRep* Icopy_zero(IntRep* old);
00091
00092
00093 class Integer
00094 {
00095 protected:
00096 IntRep* rep;
00097 public:
00098 Integer();
00099 Integer(int);
00100 Integer(long);
00101 Integer(unsigned long);
00102 Integer(IntRep*);
00103 Integer(const Integer&);
00104
00105 ~Integer();
00106 Integer& operator = (const Integer&);
00107 Integer& operator = (long);
00108
00109
00110
00111 Integer& operator ++ ();
00112 Integer& operator -- ();
00113 void negate1();
00114 void abs();
00115 void complement();
00116
00117
00118
00119 Integer& operator += (const Integer&);
00120 Integer& operator -= (const Integer&);
00121 Integer& operator *= (const Integer&);
00122 Integer& operator /= (const Integer&);
00123 Integer& operator %= (const Integer&);
00124 Integer& operator <<=(const Integer&);
00125 Integer& operator >>=(const Integer&);
00126 Integer& operator &= (const Integer&);
00127 Integer& operator |= (const Integer&);
00128 Integer& operator ^= (const Integer&);
00129
00130 Integer& operator += (long);
00131 Integer& operator -= (long);
00132 Integer& operator *= (long);
00133 Integer& operator /= (long);
00134 Integer& operator %= (long);
00135 Integer& operator <<=(long);
00136 Integer& operator >>=(long);
00137 Integer& operator &= (long);
00138 Integer& operator |= (long);
00139 Integer& operator ^= (long);
00140
00141
00142
00143 #if defined (__GNUG__) && ! defined (__STRICT_ANSI__)
00144 friend Integer operator <? (const Integer& x, const Integer& y);
00145 friend Integer operator >? (const Integer& x, const Integer& y);
00146 #endif
00147
00148
00149
00150 friend long lg (const Integer&);
00151 friend double ratio(const Integer& x, const Integer& y);
00152
00153
00154 friend Integer gcd(const Integer&, const Integer&);
00155 friend int even(const Integer&);
00156 friend int odd(const Integer&);
00157 friend int sign(const Integer&);
00158
00159 friend void (setbit)(Integer& x, long b);
00160 friend void clearbit(Integer& x, long b);
00161 friend int testbit(const Integer& x, long b);
00162
00163
00164
00165 friend void abs(const Integer& x, Integer& dest);
00166 friend void negate1(const Integer& x, Integer& dest);
00167 friend void complement(const Integer& x, Integer& dest);
00168
00169 friend int compare(const Integer&, const Integer&);
00170 friend int ucompare(const Integer&, const Integer&);
00171 friend void add(const Integer& x, const Integer& y, Integer& dest);
00172 friend void sub(const Integer& x, const Integer& y, Integer& dest);
00173 friend void mul(const Integer& x, const Integer& y, Integer& dest);
00174 friend void div(const Integer& x, const Integer& y, Integer& dest);
00175 friend void mod(const Integer& x, const Integer& y, Integer& dest);
00176 friend void divide(const Integer& x, const Integer& y, Integer& q, Integer& r);
00177 friend void _and(const Integer& x, const Integer& y, Integer& dest);
00178 friend void _or(const Integer& x, const Integer& y, Integer& dest);
00179 friend void _xor(const Integer& x, const Integer& y, Integer& dest);
00180 friend void lshift(const Integer& x, const Integer& y, Integer& dest);
00181 friend void rshift(const Integer& x, const Integer& y, Integer& dest);
00182 friend void pow(const Integer& x, const Integer& y, Integer& dest);
00183
00184 friend int compare(const Integer&, long);
00185 friend int ucompare(const Integer&, long);
00186 friend void add(const Integer& x, long y, Integer& dest);
00187 friend void sub(const Integer& x, long y, Integer& dest);
00188 friend void mul(const Integer& x, long y, Integer& dest);
00189 friend void div(const Integer& x, long y, Integer& dest);
00190 friend void mod(const Integer& x, long y, Integer& dest);
00191 friend void divide(const Integer& x, long y, Integer& q, long& r);
00192 friend void _and(const Integer& x, long y, Integer& dest);
00193 friend void _or(const Integer& x, long y, Integer& dest);
00194 friend void _xor(const Integer& x, long y, Integer& dest);
00195 friend void lshift(const Integer& x, long y, Integer& dest);
00196 friend void rshift(const Integer& x, long y, Integer& dest);
00197 friend void pow(const Integer& x, long y, Integer& dest);
00198
00199 friend int compare(long, const Integer&);
00200 friend int ucompare(long, const Integer&);
00201 friend void add(long x, const Integer& y, Integer& dest);
00202 friend void sub(long x, const Integer& y, Integer& dest);
00203 friend void mul(long x, const Integer& y, Integer& dest);
00204 friend void _and(long x, const Integer& y, Integer& dest);
00205 friend void _or(long x, const Integer& y, Integer& dest);
00206 friend void _xor(long x, const Integer& y, Integer& dest);
00207
00208
00209
00210 int fits_in_long() const { return Iislong(rep); }
00211 int fits_in_double() const;
00212
00213 long as_long() const { return Itolong(rep); }
00214 double as_double() const;
00215
00216 friend char* Itoa(const Integer& x, int base = 10, int width = 0);
00217 friend Integer atoI(const char* s, int base = 10);
00218 void printon( ostream& s, int base = 10, int width = 0) const;
00219
00220 friend ostream& operator << (ostream& s, const Integer& y);
00221 friend istream& operator >> (istream& stream, Integer& val)
00222 {
00223
00224
00225 int sign = ' ';
00226 register streambuf* sb = stream.rdbuf();
00227 int base = 10;
00228 int ndigits = 0;
00229 register int ch = sb->sbumpc();
00230 while (ch != EOF && isspace(ch))
00231 ch = sb->sbumpc();
00232 if (ch == '+' || ch == '-')
00233 {
00234 sign = ch;
00235 ch = sb->sbumpc();
00236 while (ch != EOF && isspace(ch))
00237 ch = sb->sbumpc();
00238 }
00239 if (ch == EOF) goto eof_fail;
00240 if (!(stream.flags() & ios::basefield))
00241 {
00242 if (ch == '0')
00243 {
00244 ch = sb->sbumpc();
00245 if (ch == EOF) { }
00246 else if (ch == 'x' || ch == 'X')
00247 {
00248 base = 16;
00249 ch = sb->sbumpc();
00250 if (ch == EOF) goto eof_fail;
00251 }
00252 else
00253 {
00254 sb->sputbackc(ch);
00255 base = 8;
00256 ch = '0';
00257 }
00258 }
00259 }
00260 else if ((stream.flags() & ios::basefield) == ios::hex)
00261 base = 16;
00262 else if ((stream.flags() & ios::basefield) == ios::oct)
00263 base = 8;
00264
00265 val.rep = Icopy_zero( val.rep );
00266
00267 for (;;)
00268 {
00269 if (ch == EOF)
00270 break;
00271 int digit;
00272 if (ch >= '0' && ch <= '9')
00273 digit = ch - '0';
00274 else if (ch >= 'A' && ch <= 'F')
00275 digit = ch - 'A' + 10;
00276 else if (ch >= 'a' && ch <= 'f')
00277 digit = ch - 'a' + 10;
00278 else
00279 digit = 999;
00280 if (digit >= base)
00281 {
00282 sb->sputbackc(ch);
00283 if (ndigits == 0)
00284 goto fail;
00285 else
00286 goto done;
00287 }
00288 ndigits++;
00289 switch (base)
00290 {
00291 case 8:
00292 val <<= 3;
00293 break;
00294 case 16:
00295 val <<= 4;
00296 break;
00297 default:
00298 val *= base;
00299 break;
00300 }
00301 val += digit;
00302 ch = sb->sbumpc();
00303 }
00304 fail:
00305
00306
00307 done:
00308 if (sign == '-')
00309 val.negate1();
00310 return stream;
00311 eof_fail:
00312
00313
00314 return stream;
00315 }
00316
00317
00318
00319 int initialized() const;
00320 void error(const char* msg) const;
00321 int OK( ) const;
00322 };
00323
00324
00325
00326
00327 int operator == (const Integer&, const Integer&);
00328 int operator == (const Integer&, long);
00329 int operator != (const Integer&, const Integer&);
00330 int operator != (const Integer&, long);
00331 int operator < (const Integer&, const Integer&);
00332 int operator < (const Integer&, long);
00333 int operator <= (const Integer&, const Integer&);
00334 int operator <= (const Integer&, long);
00335 int operator > (const Integer&, const Integer&);
00336 int operator > (const Integer&, long);
00337 int operator >= (const Integer&, const Integer&);
00338 int operator >= (const Integer&, long);
00339 Integer operator - (const Integer&);
00340 Integer operator ~ (const Integer&);
00341 Integer operator + (const Integer&, const Integer&);
00342 Integer operator + (const Integer&, long);
00343 Integer operator + (long, const Integer&);
00344 Integer operator - (const Integer&, const Integer&);
00345 Integer operator - (const Integer&, long);
00346 Integer operator - (long, const Integer&);
00347 Integer operator * (const Integer&, const Integer&);
00348 Integer operator * (const Integer&, long);
00349 Integer operator * (long, const Integer&);
00350 Integer operator / (const Integer&, const Integer&);
00351 Integer operator / (const Integer&, long);
00352 Integer operator % (const Integer&, const Integer&);
00353 Integer operator % (const Integer&, long);
00354 Integer operator << (const Integer&, const Integer&);
00355 Integer operator << (const Integer&, long);
00356 Integer operator >> (const Integer&, const Integer&);
00357 Integer operator >> (const Integer&, long);
00358 Integer operator & (const Integer&, const Integer&);
00359 Integer operator & (const Integer&, long);
00360 Integer operator & (long, const Integer&);
00361 Integer operator | (const Integer&, const Integer&);
00362 Integer operator | (const Integer&, long);
00363 Integer operator | (long, const Integer&);
00364 Integer operator ^ (const Integer&, const Integer&);
00365 Integer operator ^ (const Integer&, long);
00366 Integer operator ^ (long, const Integer&);
00367
00368 Integer abs(const Integer&);
00369 Integer sqr(const Integer&);
00370
00371 Integer pow(const Integer& x, const Integer& y);
00372 Integer pow(const Integer& x, long y);
00373 Integer Ipow(long x, long y);
00374
00375
00376 char* dec(const Integer& x, int width = 0);
00377 char* oct(const Integer& x, int width = 0);
00378 char* hex(const Integer& x, int width = 0);
00379 Integer sqrt(const Integer&);
00380 Integer lcm(const Integer& x, const Integer& y);
00381
00382
00383 typedef Integer IntTmp;
00384
00385 inline Integer::Integer() :rep(&_ZeroRep) {}
00386
00387 inline Integer::Integer(IntRep* r) :rep(r) {}
00388
00389 inline Integer::Integer(int y) :rep(Icopy_long(0, (long)y)) {}
00390
00391 inline Integer::Integer(long y) :rep(Icopy_long(0, y)) {}
00392
00393 inline Integer::Integer(unsigned long y) :rep(Icopy_ulong(0, y)) {}
00394
00395 inline Integer::Integer(const Integer& y) :rep(Icopy(0, y.rep)) {}
00396
00397 inline Integer::~Integer() { if (rep && !STATIC_IntRep(rep)) delete rep; }
00398
00399 inline Integer& Integer::operator = (const Integer& y)
00400 {
00401 rep = Icopy(rep, y.rep);
00402 return *this;
00403 }
00404
00405 inline Integer& Integer::operator = (long y)
00406 {
00407 rep = Icopy_long(rep, y);
00408 return *this;
00409 }
00410
00411 inline int Integer::initialized() const
00412 {
00413 return rep != 0;
00414 }
00415
00416
00417
00418 inline int compare(const Integer& x, const Integer& y)
00419 {
00420 return compare(x.rep, y.rep);
00421 }
00422
00423 inline int ucompare(const Integer& x, const Integer& y)
00424 {
00425 return ucompare(x.rep, y.rep);
00426 }
00427
00428 inline int compare(const Integer& x, long y)
00429 {
00430 return compare(x.rep, y);
00431 }
00432
00433 inline int ucompare(const Integer& x, long y)
00434 {
00435 return ucompare(x.rep, y);
00436 }
00437
00438 inline int compare(long x, const Integer& y)
00439 {
00440 return -compare(y.rep, x);
00441 }
00442
00443 inline int ucompare(long x, const Integer& y)
00444 {
00445 return -ucompare(y.rep, x);
00446 }
00447
00448 inline void add(const Integer& x, const Integer& y, Integer& dest)
00449 {
00450 dest.rep = add(x.rep, 0, y.rep, 0, dest.rep);
00451 }
00452
00453 inline void sub(const Integer& x, const Integer& y, Integer& dest)
00454 {
00455 dest.rep = add(x.rep, 0, y.rep, 1, dest.rep);
00456 }
00457
00458 inline void mul(const Integer& x, const Integer& y, Integer& dest)
00459 {
00460 dest.rep = multiply(x.rep, y.rep, dest.rep);
00461 }
00462
00463 inline void div(const Integer& x, const Integer& y, Integer& dest)
00464 {
00465 dest.rep = div(x.rep, y.rep, dest.rep);
00466 }
00467
00468 inline void mod(const Integer& x, const Integer& y, Integer& dest)
00469 {
00470 dest.rep = mod(x.rep, y.rep, dest.rep);
00471 }
00472
00473 inline void _and(const Integer& x, const Integer& y, Integer& dest)
00474 {
00475 dest.rep = bitop(x.rep, y.rep, dest.rep, '&');
00476 }
00477
00478 inline void _or(const Integer& x, const Integer& y, Integer& dest)
00479 {
00480 dest.rep = bitop(x.rep, y.rep, dest.rep, '|');
00481 }
00482
00483 inline void _xor(const Integer& x, const Integer& y, Integer& dest)
00484 {
00485 dest.rep = bitop(x.rep, y.rep, dest.rep, '^');
00486 }
00487
00488 inline void lshift(const Integer& x, const Integer& y, Integer& dest)
00489 {
00490 dest.rep = lshift(x.rep, y.rep, 0, dest.rep);
00491 }
00492
00493 inline void rshift(const Integer& x, const Integer& y, Integer& dest)
00494 {
00495 dest.rep = lshift(x.rep, y.rep, 1, dest.rep);
00496 }
00497
00498 inline void pow(const Integer& x, const Integer& y, Integer& dest)
00499 {
00500 dest.rep = power(x.rep, Itolong(y.rep), dest.rep);
00501 }
00502
00503 inline void add(const Integer& x, long y, Integer& dest)
00504 {
00505 dest.rep = add(x.rep, 0, y, dest.rep);
00506 }
00507
00508 inline void sub(const Integer& x, long y, Integer& dest)
00509 {
00510 dest.rep = add(x.rep, 0, -y, dest.rep);
00511 }
00512
00513 inline void mul(const Integer& x, long y, Integer& dest)
00514 {
00515 dest.rep = multiply(x.rep, y, dest.rep);
00516 }
00517
00518 inline void div(const Integer& x, long y, Integer& dest)
00519 {
00520 dest.rep = div(x.rep, y, dest.rep);
00521 }
00522
00523 inline void mod(const Integer& x, long y, Integer& dest)
00524 {
00525 dest.rep = mod(x.rep, y, dest.rep);
00526 }
00527
00528 inline void _and(const Integer& x, long y, Integer& dest)
00529 {
00530 dest.rep = bitop(x.rep, y, dest.rep, '&');
00531 }
00532
00533 inline void _or(const Integer& x, long y, Integer& dest)
00534 {
00535 dest.rep = bitop(x.rep, y, dest.rep, '|');
00536 }
00537
00538 inline void _xor(const Integer& x, long y, Integer& dest)
00539 {
00540 dest.rep = bitop(x.rep, y, dest.rep, '^');
00541 }
00542
00543 inline void lshift(const Integer& x, long y, Integer& dest)
00544 {
00545 dest.rep = lshift(x.rep, y, dest.rep);
00546 }
00547
00548 inline void rshift(const Integer& x, long y, Integer& dest)
00549 {
00550 dest.rep = lshift(x.rep, -y, dest.rep);
00551 }
00552
00553 inline void pow(const Integer& x, long y, Integer& dest)
00554 {
00555 dest.rep = power(x.rep, y, dest.rep);
00556 }
00557
00558 inline void abs(const Integer& x, Integer& dest)
00559 {
00560 dest.rep = abs(x.rep, dest.rep);
00561 }
00562
00563 inline void negate1(const Integer& x, Integer& dest)
00564 {
00565 dest.rep = negate1(x.rep, dest.rep);
00566 }
00567
00568 inline void complement(const Integer& x, Integer& dest)
00569 {
00570 dest.rep = _compl(x.rep, dest.rep);
00571 }
00572
00573 inline void add(long x, const Integer& y, Integer& dest)
00574 {
00575 dest.rep = add(y.rep, 0, x, dest.rep);
00576 }
00577
00578 inline void sub(long x, const Integer& y, Integer& dest)
00579 {
00580 dest.rep = add(y.rep, 1, x, dest.rep);
00581 }
00582
00583 inline void mul(long x, const Integer& y, Integer& dest)
00584 {
00585 dest.rep = multiply(y.rep, x, dest.rep);
00586 }
00587
00588 inline void _and(long x, const Integer& y, Integer& dest)
00589 {
00590 dest.rep = bitop(y.rep, x, dest.rep, '&');
00591 }
00592
00593 inline void _or(long x, const Integer& y, Integer& dest)
00594 {
00595 dest.rep = bitop(y.rep, x, dest.rep, '|');
00596 }
00597
00598 inline void _xor(long x, const Integer& y, Integer& dest)
00599 {
00600 dest.rep = bitop(y.rep, x, dest.rep, '^');
00601 }
00602
00603
00604
00605
00606 inline int operator == (const Integer& x, const Integer& y)
00607 {
00608 return compare(x, y) == 0;
00609 }
00610
00611 inline int operator == (const Integer& x, long y)
00612 {
00613 return compare(x, y) == 0;
00614 }
00615
00616 inline int operator != (const Integer& x, const Integer& y)
00617 {
00618 return compare(x, y) != 0;
00619 }
00620
00621 inline int operator != (const Integer& x, long y)
00622 {
00623 return compare(x, y) != 0;
00624 }
00625
00626 inline int operator < (const Integer& x, const Integer& y)
00627 {
00628 return compare(x, y) < 0;
00629 }
00630
00631 inline int operator < (const Integer& x, long y)
00632 {
00633 return compare(x, y) < 0;
00634 }
00635
00636 inline int operator <= (const Integer& x, const Integer& y)
00637 {
00638 return compare(x, y) <= 0;
00639 }
00640
00641 inline int operator <= (const Integer& x, long y)
00642 {
00643 return compare(x, y) <= 0;
00644 }
00645
00646 inline int operator > (const Integer& x, const Integer& y)
00647 {
00648 return compare(x, y) > 0;
00649 }
00650
00651 inline int operator > (const Integer& x, long y)
00652 {
00653 return compare(x, y) > 0;
00654 }
00655
00656 inline int operator >= (const Integer& x, const Integer& y)
00657 {
00658 return compare(x, y) >= 0;
00659 }
00660
00661 inline int operator >= (const Integer& x, long y)
00662 {
00663 return compare(x, y) >= 0;
00664 }
00665
00666
00667 inline Integer& Integer::operator += (const Integer& y)
00668 {
00669 add(*this, y, *this);
00670 return *this;
00671 }
00672
00673 inline Integer& Integer::operator += (long y)
00674 {
00675 add(*this, y, *this);
00676 return *this;
00677 }
00678
00679 inline Integer& Integer::operator ++ ()
00680 {
00681 add(*this, 1, *this);
00682 return *this;
00683 }
00684
00685
00686 inline Integer& Integer::operator -= (const Integer& y)
00687 {
00688 sub(*this, y, *this);
00689 return *this;
00690 }
00691
00692 inline Integer& Integer::operator -= (long y)
00693 {
00694 sub(*this, y, *this);
00695 return *this;
00696 }
00697
00698 inline Integer& Integer::operator -- ()
00699 {
00700 add(*this, -1, *this);
00701 return *this;
00702 }
00703
00704
00705
00706 inline Integer& Integer::operator *= (const Integer& y)
00707 {
00708 mul(*this, y, *this);
00709 return *this;
00710 }
00711
00712 inline Integer& Integer::operator *= (long y)
00713 {
00714 mul(*this, y, *this);
00715 return *this;
00716 }
00717
00718
00719 inline Integer& Integer::operator &= (const Integer& y)
00720 {
00721 _and(*this, y, *this);
00722 return *this;
00723 }
00724
00725 inline Integer& Integer::operator &= (long y)
00726 {
00727 _and(*this, y, *this);
00728 return *this;
00729 }
00730
00731 inline Integer& Integer::operator |= (const Integer& y)
00732 {
00733 _or(*this, y, *this);
00734 return *this;
00735 }
00736
00737 inline Integer& Integer::operator |= (long y)
00738 {
00739 _or(*this, y, *this);
00740 return *this;
00741 }
00742
00743
00744 inline Integer& Integer::operator ^= (const Integer& y)
00745 {
00746 _xor(*this, y, *this);
00747 return *this;
00748 }
00749
00750 inline Integer& Integer::operator ^= (long y)
00751 {
00752 _xor(*this, y, *this);
00753 return *this;
00754 }
00755
00756
00757
00758 inline Integer& Integer::operator /= (const Integer& y)
00759 {
00760 div(*this, y, *this);
00761 return *this;
00762 }
00763
00764 inline Integer& Integer::operator /= (long y)
00765 {
00766 div(*this, y, *this);
00767 return *this;
00768 }
00769
00770
00771 inline Integer& Integer::operator <<= (const Integer& y)
00772 {
00773 lshift(*this, y, *this);
00774 return *this;
00775 }
00776
00777 inline Integer& Integer::operator <<= (long y)
00778 {
00779 lshift(*this, y, *this);
00780 return *this;
00781 }
00782
00783
00784 inline Integer& Integer::operator >>= (const Integer& y)
00785 {
00786 rshift(*this, y, *this);
00787 return *this;
00788 }
00789
00790 inline Integer& Integer::operator >>= (long y)
00791 {
00792 rshift(*this, y, *this);
00793 return *this;
00794 }
00795
00796 #if defined (__GNUG__) && ! defined (__STRICT_ANSI__)
00797 inline Integer operator <? (const Integer& x, const Integer& y)
00798 {
00799 return (compare(x.rep, y.rep) <= 0) ? x : y;
00800 }
00801
00802 inline Integer operator >? (const Integer& x, const Integer& y)
00803 {
00804 return (compare(x.rep, y.rep) >= 0)? x : y;
00805 }
00806 #endif
00807
00808
00809 inline void Integer::abs()
00810 {
00811 ::abs(*this, *this);
00812 }
00813
00814 inline void Integer::negate1()
00815 {
00816 ::negate1(*this, *this);
00817 }
00818
00819
00820 inline void Integer::complement()
00821 {
00822 ::complement(*this, *this);
00823 }
00824
00825
00826 inline int sign(const Integer& x)
00827 {
00828 return (x.rep->len == 0) ? 0 : ( (x.rep->sgn == 1) ? 1 : -1 );
00829 }
00830
00831 inline int even(const Integer& y)
00832 {
00833 return y.rep->len == 0 || !(y.rep->s[0] & 1);
00834 }
00835
00836 inline int odd(const Integer& y)
00837 {
00838 return y.rep->len > 0 && (y.rep->s[0] & 1);
00839 }
00840
00841 inline char* Itoa(const Integer& y, int base, int width)
00842 {
00843 return Itoa(y.rep, base, width);
00844 }
00845
00846
00847
00848 inline long lg(const Integer& x)
00849 {
00850 return lg(x.rep);
00851 }
00852
00853
00854
00855 #if defined(__GNUG__) && !defined(_G_NO_NRV)
00856
00857 inline Integer operator + (const Integer& x, const Integer& y)
00858 {
00859 Integer r;
00860 add(x, y, r);
00861 return r;
00862 }
00863
00864 inline Integer operator + (const Integer& x, long y)
00865 {
00866 Integer r;
00867 add(x, y, r);
00868 return r;
00869 }
00870
00871 inline Integer operator + (long x, const Integer& y)
00872 {
00873 Integer r;
00874 add(x, y, r);
00875 return r;
00876 }
00877
00878 inline Integer operator - (const Integer& x, const Integer& y)
00879 {
00880 Integer r;
00881 sub(x, y, r);
00882 return r;
00883 }
00884
00885 inline Integer operator - (const Integer& x, long y)
00886 {
00887 Integer r;
00888 sub(x, y, r);
00889 return r;
00890 }
00891
00892 inline Integer operator - (long x, const Integer& y)
00893 {
00894 Integer r;
00895 sub(x, y, r);
00896 return r;
00897 }
00898
00899 inline Integer operator * (const Integer& x, const Integer& y)
00900 {
00901 Integer r;
00902 mul(x, y, r);
00903 return r;
00904 }
00905
00906 inline Integer operator * (const Integer& x, long y)
00907 {
00908 Integer r;
00909 mul(x, y, r);
00910 return r;
00911 }
00912
00913 inline Integer operator * (long x, const Integer& y)
00914 {
00915 Integer r;
00916 mul(x, y, r);
00917 return r;
00918 }
00919
00920 inline Integer sqr(const Integer& x)
00921 {
00922 Integer r;
00923 mul(x, x, r);
00924 return r;
00925 }
00926
00927 inline Integer operator & (const Integer& x, const Integer& y)
00928 {
00929 Integer r;
00930 _and(x, y, r);
00931 return r;
00932 }
00933
00934 inline Integer operator & (const Integer& x, long y)
00935 {
00936 Integer r;
00937 _and(x, y, r);
00938 return r;
00939 }
00940
00941 inline Integer operator & (long x, const Integer& y)
00942 {
00943 Integer r;
00944 _and(x, y, r);
00945 return r;
00946 }
00947
00948 inline Integer operator | (const Integer& x, const Integer& y)
00949 {
00950 Integer r;
00951 _or(x, y, r);
00952 return r;
00953 }
00954
00955 inline Integer operator | (const Integer& x, long y)
00956 {
00957 Integer r;
00958 _or(x, y, r);
00959 return r;
00960 }
00961
00962 inline Integer operator | (long x, const Integer& y)
00963 {
00964 Integer r;
00965 _or(x, y, r);
00966 return r;
00967 }
00968
00969 inline Integer operator ^ (const Integer& x, const Integer& y)
00970 {
00971 Integer r;
00972 _xor(x, y, r);
00973 return r;
00974 }
00975
00976 inline Integer operator ^ (const Integer& x, long y)
00977 {
00978 Integer r;
00979 _xor(x, y, r);
00980 return r;
00981 }
00982
00983 inline Integer operator ^ (long x, const Integer& y)
00984 {
00985 Integer r;
00986 _xor(x, y, r);
00987 return r;
00988 }
00989
00990 inline Integer operator / (const Integer& x, const Integer& y)
00991 {
00992 Integer r;
00993 div(x, y, r);
00994 return r;
00995 }
00996
00997 inline Integer operator / (const Integer& x, long y)
00998 {
00999 Integer r;
01000 div(x, y, r);
01001 return r;
01002 }
01003
01004 inline Integer operator % (const Integer& x, const Integer& y)
01005 {
01006 Integer r;
01007 mod(x, y, r);
01008 return r;
01009 }
01010
01011 inline Integer operator % (const Integer& x, long y)
01012 {
01013 Integer r;
01014 mod(x, y, r);
01015 return r;
01016 }
01017
01018 inline Integer operator << (const Integer& x, const Integer& y)
01019 {
01020 Integer r;
01021 lshift(x, y, r);
01022 return r;
01023 }
01024
01025 inline Integer operator << (const Integer& x, long y)
01026 {
01027 Integer r;
01028 lshift(x, y, r);
01029 return r;
01030 }
01031
01032 inline Integer operator >> (const Integer& x, const Integer& y)
01033 {
01034 Integer r;
01035 rshift(x, y, r);
01036 return r;
01037 }
01038
01039 inline Integer operator >> (const Integer& x, long y)
01040 {
01041 Integer r;
01042 rshift(x, y, r);
01043 return r;
01044 }
01045
01046 inline Integer pow(const Integer& x, long y)
01047 {
01048 Integer r;
01049 pow(x, y, r);
01050 return r;
01051 }
01052
01053
01054
01055
01056
01057
01058
01059
01060 inline Integer pow(const Integer& x, const Integer& y)
01061 {
01062 Integer r;
01063 pow(x, y, r);
01064 return r;
01065 }
01066
01067
01068
01069 inline Integer abs(const Integer& x)
01070 {
01071 Integer r;
01072 abs(x, r);
01073 return r;
01074 }
01075
01076 inline Integer operator - (const Integer& x)
01077 {
01078 Integer r;
01079 negate1(x, r);
01080 return r;
01081 }
01082
01083 inline Integer operator ~ (const Integer& x)
01084 {
01085 Integer r;
01086 complement(x, r);
01087 return r;
01088 }
01089
01090 inline Integer atoI(const char* s, int base)
01091 {
01092 Integer r;
01093 r.rep = atoIntRep(s, base);
01094 return r;
01095 }
01096
01097 inline Integer gcd(const Integer& x, const Integer& y)
01098 {
01099 Integer r;
01100 r.rep = gcd(x.rep, y.rep);
01101 return r;
01102 }
01103
01104 #else
01105
01106 inline Integer operator + (const Integer& x, const Integer& y)
01107 {
01108 Integer r; add(x, y, r); return r;
01109 }
01110
01111 inline Integer operator + (const Integer& x, long y)
01112 {
01113 Integer r; add(x, y, r); return r;
01114 }
01115
01116 inline Integer operator + (long x, const Integer& y)
01117 {
01118 Integer r; add(x, y, r); return r;
01119 }
01120
01121 inline Integer operator - (const Integer& x, const Integer& y)
01122 {
01123 Integer r; sub(x, y, r); return r;
01124 }
01125
01126 inline Integer operator - (const Integer& x, long y)
01127 {
01128 Integer r; sub(x, y, r); return r;
01129 }
01130
01131 inline Integer operator - (long x, const Integer& y)
01132 {
01133 Integer r; sub(x, y, r); return r;
01134 }
01135
01136 inline Integer operator * (const Integer& x, const Integer& y)
01137 {
01138 Integer r; mul(x, y, r); return r;
01139 }
01140
01141 inline Integer operator * (const Integer& x, long y)
01142 {
01143 Integer r; mul(x, y, r); return r;
01144 }
01145
01146 inline Integer operator * (long x, const Integer& y)
01147 {
01148 Integer r; mul(x, y, r); return r;
01149 }
01150
01151 inline Integer sqr(const Integer& x)
01152 {
01153 Integer r; mul(x, x, r); return r;
01154 }
01155
01156 inline Integer operator & (const Integer& x, const Integer& y)
01157 {
01158 Integer r; _and(x, y, r); return r;
01159 }
01160
01161 inline Integer operator & (const Integer& x, long y)
01162 {
01163 Integer r; _and(x, y, r); return r;
01164 }
01165
01166 inline Integer operator & (long x, const Integer& y)
01167 {
01168 Integer r; _and(x, y, r); return r;
01169 }
01170
01171 inline Integer operator | (const Integer& x, const Integer& y)
01172 {
01173 Integer r; _or(x, y, r); return r;
01174 }
01175
01176 inline Integer operator | (const Integer& x, long y)
01177 {
01178 Integer r; _or(x, y, r); return r;
01179 }
01180
01181 inline Integer operator | (long x, const Integer& y)
01182 {
01183 Integer r; _or(x, y, r); return r;
01184 }
01185
01186 inline Integer operator ^ (const Integer& x, const Integer& y)
01187 {
01188 Integer r; _xor(x, y, r); return r;
01189 }
01190
01191 inline Integer operator ^ (const Integer& x, long y)
01192 {
01193 Integer r; _xor(x, y, r); return r;
01194 }
01195
01196 inline Integer operator ^ (long x, const Integer& y)
01197 {
01198 Integer r; _xor(x, y, r); return r;
01199 }
01200
01201 inline Integer operator / (const Integer& x, const Integer& y)
01202 {
01203 Integer r; div(x, y, r); return r;
01204 }
01205
01206 inline Integer operator / (const Integer& x, long y)
01207 {
01208 Integer r; div(x, y, r); return r;
01209 }
01210
01211 inline Integer operator % (const Integer& x, const Integer& y)
01212 {
01213 Integer r; mod(x, y, r); return r;
01214 }
01215
01216 inline Integer operator % (const Integer& x, long y)
01217 {
01218 Integer r; mod(x, y, r); return r;
01219 }
01220
01221 inline Integer operator << (const Integer& x, const Integer& y)
01222 {
01223 Integer r; lshift(x, y, r); return r;
01224 }
01225
01226 inline Integer operator << (const Integer& x, long y)
01227 {
01228 Integer r; lshift(x, y, r); return r;
01229 }
01230
01231 inline Integer operator >> (const Integer& x, const Integer& y)
01232 {
01233 Integer r; rshift(x, y, r); return r;
01234 }
01235
01236 inline Integer operator >> (const Integer& x, long y)
01237 {
01238 Integer r; rshift(x, y, r); return r;
01239 }
01240
01241 inline Integer pow(const Integer& x, long y)
01242 {
01243 Integer r; pow(x, y, r); return r;
01244 }
01245
01246 inline Integer Ipow(long x, long y)
01247 {
01248 Integer r(x); pow(r, y, r); return r;
01249 }
01250
01251 inline Integer pow(const Integer& x, const Integer& y)
01252 {
01253 Integer r; pow(x, y, r); return r;
01254 }
01255
01256
01257
01258 inline Integer abs(const Integer& x)
01259 {
01260 Integer r; abs(x, r); return r;
01261 }
01262
01263 inline Integer operator - (const Integer& x)
01264 {
01265 Integer r; negate1(x, r); return r;
01266 }
01267
01268 inline Integer operator ~ (const Integer& x)
01269 {
01270 Integer r; complement(x, r); return r;
01271 }
01272
01273 inline Integer atoI(const char* s, int base)
01274 {
01275 Integer r; r.rep = atoIntRep(s, base); return r;
01276 }
01277
01278 inline Integer gcd(const Integer& x, const Integer& y)
01279 {
01280 Integer r; r.rep = gcd(x.rep, y.rep); return r;
01281 }
01282
01283 #endif
01284
01285 inline Integer& Integer::operator %= (const Integer& y)
01286 {
01287 *this = *this % y;
01288 return *this;
01289 }
01290
01291 inline Integer& Integer::operator %= (long y)
01292 {
01293 *this = *this % y;
01294 return *this;
01295 }
01296 #endif