fork download

copy

#include <iostream>
#include <cstdio>
#include <cstdlib>
//#include <stdlib.h>
#include <cstdint>
#include <cassert>
#include <string>
 
typedef int64_t CONTAINER; /* not uint64_t, because using minus-number in mpz_class::operator-() */
unsigned int BIT = 3; /* BIT <= 64bit - 2bit = 62bit */
 
CONTAINER CMASK = 1ULL << BIT;
CONTAINER BMASK = CMASK - 1;
 
namespace QZ {
  class mpz_base_class {
 
  private:
    unsigned int n;
    CONTAINER *b;
 
  private:
    static void LeftShift(mpz_base_class &a);
    static void RightShift(mpz_base_class &a, int &lsb_out);
    static void LeftShift2(int &msb, mpz_base_class &a);
    static void LeftShift3(mpz_base_class &a, int msb);
 
  protected:
 
 
  public:
    static bool iszero(mpz_base_class const &n);
    static void div2(mpz_base_class const &a, mpz_base_class const &b, mpz_base_class &q, mpz_base_class &r);
 
    mpz_base_class(); //
    virtual ~mpz_base_class();
    mpz_base_class(const unsigned long c);
    mpz_base_class(mpz_base_class const &ob);
    mpz_base_class &operator=(mpz_base_class const &ob);
//  mpz_base_class &operator=(mpz_base_class const &&ob);
 
    friend bool operator==(mpz_base_class const &a, mpz_base_class const &b);
    friend bool operator!=(mpz_base_class const &a, mpz_base_class const &b) { return !(a == b); }
 
    friend std::ostream &operator<<(std::ostream &stream, mpz_base_class c);
 
    friend mpz_base_class operator+(mpz_base_class const &a, mpz_base_class const &b);
    friend mpz_base_class operator-(mpz_base_class const &a, mpz_base_class const &b);
    mpz_base_class operator++(int dmy) { mpz_base_class r = *this; *this = *this + 1; return r; }
    mpz_base_class operator--(int dmy) { mpz_base_class r = *this; *this = *this - 1; return r; }
    mpz_base_class &operator++() { *this = *this + 1; return *this; }
    mpz_base_class &operator--() { *this = *this - 1; return *this; }
    mpz_base_class &operator+() { return *this; }
    mpz_base_class operator-() = delete;
 
    mpz_base_class operator~() = delete;
    explicit operator bool() const { return *this != 0; }
    bool operator!() const { return !static_cast<bool>(*this); }
 
    friend bool operator<(mpz_base_class const &a, mpz_base_class const &b);
    friend bool operator<=(mpz_base_class const &a, mpz_base_class const &b) { return (a < b) ? true : (a == b) ? true : false; }
    friend bool operator>(mpz_base_class const &a, mpz_base_class const &b) { return (a < b) ? false : (a == b) ? false : true; }
    friend bool operator>=(mpz_base_class const &a, mpz_base_class const &b) { return (a < b) ? false : (a == b) ? true : true; }
 
    friend mpz_base_class operator*(mpz_base_class const &a, mpz_base_class const &b);
    friend mpz_base_class operator/(mpz_base_class const &a, mpz_base_class const &b) { mpz_base_class q, r; div2(a, b, q, r); return q; }
    friend mpz_base_class operator%(mpz_base_class const &a, mpz_base_class const &b) { mpz_base_class q, r; div2(a, b, q, r); return r; }
 
    mpz_base_class &operator+=(mpz_base_class const &ob) { *this = *this + ob; return *this; }
    mpz_base_class &operator-=(mpz_base_class const &ob) { *this = *this - ob; return *this; }
    mpz_base_class &operator*=(mpz_base_class const &ob) { *this = *this * ob; return *this; }
    mpz_base_class &operator/=(mpz_base_class const &ob) { *this = *this / ob; return *this; }
    mpz_base_class &operator%=(mpz_base_class const &ob) { *this = *this % ob; return *this; }
    mpz_base_class &operator&=(mpz_base_class const &ob) = delete;
    mpz_base_class &operator|=(mpz_base_class const &ob) = delete;
    mpz_base_class &operator^=(mpz_base_class const &ob) = delete;
 
    bool testBit(int n);
    mpz_base_class operator>>(int n) const { int dmy; mpz_base_class r = *this; for (int i = 0; i < n; i++) RightShift(r, dmy); return r; }
    mpz_base_class operator<<(int n) const { mpz_base_class r = *this; for (int i = 0; i < n; i++) LeftShift(r); return r; }
    mpz_base_class &operator>>=(int n) { *this = *this >> n; return *this; }
    mpz_base_class &operator<<=(int n) { *this = *this << n; return *this; }
 
    int bitLength();
 
    /* for test */
    unsigned int get_mpzclass_n() { return this->n; }
    CONTAINER *get_mpzclass_b() { return this->b; }
    virtual void dump() const {
      std::cout << "n = " << this->n << ": ";
      for (unsigned int i = 0; i < this->n; i++)
        std::cout << i << ":" << this->b[i] << ",";
      std::cout << std::endl;
    }
 
    void test42() {
      // *this == 4 + 256;
      this->b[2] = 0;
    }
  };
 
  class mpz_class {
  private:
    mpz_base_class base;
    bool negative;
 
  public:
    mpz_class();
    ~mpz_class();
    mpz_class(const signed long c);
    mpz_class(mpz_class const &ob);
    mpz_class &operator=(mpz_class const &ob);
//  mpz_class &operator=(mpz_class const &&ob);
//  mpz_class &operator=(mpz_base_class const &ob); // mpz_base_class と mpz_class の関係を、継承から委譲に変更した時に不要となった
 
    friend bool operator==(mpz_class const &a, mpz_class const &b) { return (a.base == b.base) && (a.negative == b.negative); }
    friend bool operator!=(mpz_class const &a, mpz_class const &b) { return !(a == b); }
 
    friend std::ostream &operator<<(std::ostream &stream, mpz_class c);
 
    mpz_class operator-() const { mpz_class r = *this; r.negative = !r.negative; return r; }
    mpz_class &operator+() { return *this; }
 
    friend bool operator<(mpz_class const &a, mpz_class const &b);
    friend bool operator<=(mpz_class const &a, mpz_class const &b) { return (a < b) ? true : (a == b) ? true : false; }
    friend bool operator>(mpz_class const &a, mpz_class const &b) { return (a < b) ? false : (a == b) ? false : true; }
    friend bool operator>=(mpz_class const &a, mpz_class const &b) { return (a < b) ? false : (a == b) ? true : true; }
 
    friend mpz_class operator+(mpz_class const &a, mpz_class const &b);
    friend mpz_class operator-(mpz_class const &a, mpz_class const &b);
    mpz_class operator++(int dmy) { mpz_class r = *this; *this = *this + 1; return r; }
    mpz_class operator--(int dmy) { mpz_class r = *this; *this = *this - 1; return r; }
    mpz_class &operator++() { *this = *this + 1; return *this; }
    mpz_class &operator--() { *this = *this - 1; return *this; }
 
    mpz_class operator~() = delete;
    explicit operator bool() const { return *this != 0; }
    bool operator!() const { return !static_cast<bool>(*this); }
 
    friend mpz_class operator*(mpz_class const &a, mpz_class const &b);
    friend mpz_class operator/(mpz_class const &a, mpz_class const &b);
    friend mpz_class operator%(mpz_class const &a, mpz_class const &b);
 
    mpz_class &operator+=(mpz_class const &n) { *this = *this + n; return *this; }
    mpz_class &operator-=(mpz_class const &n) { *this = *this - n; return *this; }
    mpz_class &operator*=(mpz_class const &n) { *this = *this * n; return *this; }
    mpz_class &operator/=(mpz_class const &n) { *this = *this / n; return *this; }
    mpz_class &operator%=(mpz_class const &n) { *this = *this % n; return *this; }
    mpz_class &operator&=(mpz_class const &ob) = delete;
    mpz_class &operator|=(mpz_class const &ob) = delete;
    mpz_class &operator^=(mpz_class const &ob) = delete;
 
    mpz_class operator>>(int n) { mpz_class r = *this; r.base >>= n; return r; }
    mpz_class operator<<(int n) { mpz_class r = *this; r.base <<= n; return r; }
    mpz_class &operator>>=(int n) { *this = *this >> n; return *this; }
    mpz_class &operator<<=(int n) { *this = *this << n; return *this; }
 
    int bitLength();
 
    bool get_mpzclass_negative() { return this->negative; }
 
    virtual void dump() const {
      this->base.dump();
      std::cout << "sign = " << this->negative << std::endl;
    }
 
/* for test */
    mpz_base_class get_mpzclass_base() { return this->base; }
 
  };
 
  mpz_base_class::mpz_base_class() {
//    std::cout << "mpz_base_class constructor1" << std::endl;
    this->n = 0;
    this->b = 0;
  }  
  mpz_base_class::~mpz_base_class() {
//    std::cout << "mpz_base_class destructor" << std::endl;
    if (this->b) delete [] this->b;
    this->n = 0;
    this->b = 0;
  }
  mpz_base_class::mpz_base_class(const unsigned long c) {
//    std::cout << "mpz_base_class constructor2" << std::endl;
    CONTAINER cc;
    cc = c;
    if (c == 0) {
      this->n = 1;
      this->b = new CONTAINER [1];
      this->b[0] = 0;
      return;
    }
 
    assert(cc > 0);
 
    CONTAINER *newbody;
    unsigned int i, j, r, pos;
 
    this->b = 0;
    this->n = 0;
 
    while (cc > 0) {
      r = 0;
      pos = 1;
      for (i = 0; i < BIT; i++) {
        if ((cc & 1) != 0) {
          r = (r | pos);
        } else {
        }
        pos = pos * 2;
        cc = cc / 2;
      }
      newbody = new CONTAINER [this->n + 1];
      for (j = 0; j < this->n; j++)
        newbody[j] = this->b[j];
      newbody[j] = r;
      delete [] this->b;
      this->b = newbody;
      this->n++;
    }
    assert(this->n != 0);
  }
 
  mpz_base_class::mpz_base_class(const mpz_base_class &ob) {
//    std::cout << "mpz_base_class constructor3" << std::endl;
    this->n = ob.n;
    if (ob.n == 0) {
      this->b = 0;
    } else {
      this->b = new CONTAINER [ob.n];
      for (unsigned int i = 0; i < ob.n; i++)
        this->b[i] = ob.b[i];
    }
    assert((this->n == 0 && this->b == 0) || (this->n > 0 && this->b != 0));
  }
 
  mpz_base_class &mpz_base_class::operator=(const mpz_base_class &ob) {
//    std::cout << "mpz_base_class operator=" << std::endl;
    CONTAINER *org_b = this->b; // for checking self-assignment
    this->n = ob.n;
    if (ob.n == 0) {
      this->b = 0;
      delete [] org_b;
    } else {
      this->b = new CONTAINER [ob.n];
      for (unsigned int i = 0; i < ob.n; i++)
        this->b[i] = ob.b[i];
      delete [] org_b;
    }
    assert((this->n == 0 && this->b == 0) || (this->n > 0 && this->b != 0));
    return *this;
  }
 
  bool operator==(mpz_base_class const &a, mpz_base_class const &b) {
//    std::cout << "mpz_base_class operator==" << std::endl;
    unsigned int i, less;
    bool isEqual = true;
 
    if (a.n < b.n)
      less = a.n;
    else
      less = b.n;
    for (i = 0; i < less; i++)
      if (a.b[i] != b.b[i]) {
        isEqual = false;
        goto label;
      }
    if (a.n < b.n) {
      for (; i < b.n; i++)
        if (b.b[i] != 0) {
          isEqual = false;
          goto label;
        }
    } else {
      for (; i < a.n; i++)
        if (a.b[i] != 0) { // be carefull! not b.b[] but a.b[]
          isEqual = false;
          goto label;
        }
    }
  label:
    return isEqual;
  }
 
 
  std::ostream &operator<<(std::ostream &stream, mpz_base_class c) {
//    std::cout << "mpz_base_class operator<<" << std::endl;
    std::basic_string<char> mod10;
    mpz_base_class q, n;
    int mod;
    bool fzero;
 
    fzero = true;
    n = c;
    for(;;) {
      /* div10(n, q, mod); */
      {
        q = n;
        mod = 0;
        for (unsigned int i = 0; i < n.n * BIT; i++) {
          /* shift_div(mod, q); */
          {
            unsigned int cy, i;
 
            cy = 0;
            for (i = 0; i < n.n; i++) {
              q.b[i] = q.b[i] << 1;
              if (cy)
                q.b[i] = q.b[i] | 0x01;
              cy = (q.b[i] >> BIT);
              q.b[i] = q.b[i] & BMASK;
            }
            mod = mod << 1;
            if (cy)
              mod = mod | 0x01;
 
          }
          if (mod >= 10) {
            q.b[0] = q.b[0] | 0x01;
            mod = mod - 10;
          }
        }
      }
      if (mpz_base_class::iszero(q) && mod == 0)
        break;
      mod10 = (char)('0' + mod) + mod10;
      fzero = false;
      n = q;
    }
 
    if (fzero)
      stream << '0';
    else
      stream << mod10;
    return stream;
  }
 
  mpz_base_class operator+(mpz_base_class const &a, mpz_base_class const &b) {
    mpz_base_class r;
    mpz_base_class const * more_ab;
    unsigned int less_n;
    if (a.n > b.n) {
      r.n = a.n;
      more_ab = &a;
      less_n = b.n;
    } else {
      r.n = b.n;
      more_ab = &b;
      less_n = a.n;
    }
    r.b = new CONTAINER [r.n];
    unsigned int i, carry = 0;
    for (i = 0; i < less_n; i++) {
      CONTAINER s = a.b[i] + b.b[i] + carry;
      if (s >= CMASK) {
        carry = 1;
        r.b[i] = (s  & BMASK);
      } else {
        carry = 0;
        r.b[i] = s; /* need */
      }
    }
    for (;i < r.n; i++) {
      CONTAINER s = more_ab->b[i] + carry;
      if (s >= CMASK) {
        carry = 1;
        r.b[i] = (s  & BMASK); /* need */
      } else {
        carry = 0;
        r.b[i] = (s  & BMASK); /* need */ /* do not to insert break keyword.*/
      }
    }
    if (carry) {
      CONTAINER *new_body = new CONTAINER [r.n + 1];
      for (i = 0; i < r.n; i++)
        new_body[i] = r.b[i];
      new_body[i] = carry;
      delete [] r.b;
      r.b = new_body;
      // r.b[r.n] = 1; /* NOT need */
      r.n++;
    }
    return r;
  }
 
 
  bool mpz_base_class::iszero(mpz_base_class const &n) {
    bool isZero = true;
    for (unsigned int i = 0; i < n.n; i++)
      if (n.b[i] != 0) {
        isZero = false;
        break;
      }
    return isZero;
  }
 
  mpz_base_class operator-(mpz_base_class const &a, mpz_base_class const &b) {
    int vCount, moreCount, i;
    CONTAINER diff;
    int borrowR = 0;
    bool flagMore, flagLess;
    mpz_base_class r;
    flagMore = false;
    flagLess = false;
    moreCount = a.n;
    vCount = a.n;
    r = a;
    if (a.n > b.n) {
      flagMore = true;
      vCount = b.n;
      moreCount = a.n;
      r = a;
    }
    if (a.n < b.n) {
      flagLess = true;
      vCount = a.n;  
      moreCount = b.n;
      r = b;
    }
 
    borrowR = 0;
    for (i = 0; i < vCount; i++) {
      diff = a.b[i] - b.b[i] - borrowR;
      if (diff < 0) {
        borrowR = 1;
        r.b[i] = diff + CMASK;
      } else {
        borrowR = 0;
        r.b[i] = diff;
      }
    }
    if (flagMore) {
      for (;i < moreCount; i++) {
        diff = a.b[i] - borrowR;
        if (diff < 0) {
          borrowR = 1;
          r.b[i] = diff + CMASK;
        } else {
          borrowR = 0;
          r.b[i] = diff;
        }
      }
    }
    if (flagLess) {
      for (;i < moreCount; i++) {
        if (b.b[i] > 0) {
          borrowR = 1;
        }
      }
    }
    if (borrowR > 0) throw std::underflow_error("negative value.");
    return r;
  }
 
  bool operator<(mpz_base_class const &a, mpz_base_class const &b) { // if a < b then true
    try {
      mpz_base_class r = a - b;
    } catch (std::underflow_error &e) {
      return true;
    }
    return false;
  }
 
  mpz_base_class operator*(mpz_base_class const &a, mpz_base_class const &b) {
    mpz_base_class Rshift = b;
    mpz_base_class Lshift = a;
    mpz_base_class r = 0;
    int lsb;
    while (!mpz_base_class::iszero(Rshift)) {
      mpz_base_class::RightShift(Rshift, lsb);
      if (lsb) {
        r = r + Lshift;
      }
      mpz_base_class::LeftShift(Lshift);
    }
    return r;
  }
 
  void mpz_base_class::LeftShift(mpz_base_class &a) {
    unsigned int i, msb;
    msb = 0;
    for (i = 0; i < a.n; i++) {
      a.b[i] *= 2;
      if (msb > 0)
        a.b[i] = (a.b[i] | 0x01);
 
      if (a.b[i] > BMASK) {
        msb = 1;
        a.b[i] -= CMASK;
      } else {
        msb = 0;
      }
    }
    if (msb > 0) {
      CONTAINER *newbody;
      newbody = new CONTAINER [a.n + 1];
      newbody[a.n] = 1;
      for (unsigned int i = 0; i < a.n; i++) {
        newbody[i] = a.b[i];
      }
      a.n++;
      delete [] a.b;
      a.b = newbody;
    }
  }
 
  void mpz_base_class::RightShift(mpz_base_class &a, int &lsb_out) {
    int i, lsb;
    lsb = 0;
    for (i = a.n - 1; i >= 0; --i) {
      if (lsb > 0)
        a.b[i] = (a.b[i] | CMASK);
 
      if ((a.b[i] & 0x01) > 0)
        lsb = 1;
      else
        lsb = 0;
      a.b[i] /= 2;
    }
    lsb_out = lsb;
    if (a.b[a.n - 1] == 0) {
      CONTAINER *newbody;
      newbody = new CONTAINER [a.n - 1];
      for (unsigned int i = 0; i < a.n - 1; i++)
        newbody[i] = a.b[i];
      a.n--;
      delete [] a.b;
      a.b = newbody;
    }
  }
 
  void mpz_base_class::LeftShift2(int &msb, mpz_base_class &a) {
    unsigned int i, msb_v;
    msb_v = 0;
    for (i = 0; i < a.n; i++) {
      a.b[i] *= 2;
      if (msb_v > 0)
        a.b[i] = (a.b[i] | 0x01);
 
      if (a.b[i] > BMASK) {
        msb_v = 1;
        a.b[i] -= CMASK;
      } else {
        msb_v = 0;
      }
    }
    msb = msb_v;
  }
 
  void mpz_base_class::LeftShift3(mpz_base_class &a, int msb) {
    unsigned int i, msb_v;
    msb_v = msb;
    for (i = 0; i < a.n; i++) {
      a.b[i] *= 2;
      if (msb_v > 0)
        a.b[i] = (a.b[i] | 0x01);
 
      if (a.b[i] > BMASK) {
        msb_v = 1;
        a.b[i] -= CMASK;
      } else {
        msb_v = 0;
      }
    }
    if (msb_v > 0) {
      CONTAINER *newbody;
      newbody = new CONTAINER [a.n + 1];
      newbody[a.n] = 1;
      for (unsigned int i = 0; i < a.n; i++) {
        newbody[i] = a.b[i];
      }
      a.n++;
      delete [] a.b;
      a.b = newbody;
    }
  }
  void mpz_base_class::div2(mpz_base_class const &a, mpz_base_class const &b, mpz_base_class &q, mpz_base_class &r) {
    if (b == mpz_base_class(0)) {
      std::cout << "null devided." << std::endl;
      return;
    }
 
    /* LeftRest <- LeftShiftBuff */
    mpz_base_class LeftRest(0);
    mpz_base_class LeftShiftBuff = a;
    mpz_base_class Quotient(0);
    int msb, lsb;
    msb = 0;
    int n = a.n * BIT;
    while (n > 0) {
      //    std::cout << "LeftShiftBuff=" << LeftShiftBuff << std::endl;
      //    std::cout << "LeftRest=" << LeftRest << std::endl;
      mpz_base_class::LeftShift2(msb, LeftShiftBuff);
      mpz_base_class::LeftShift3(LeftRest, msb);
      lsb = 0;
      if (b < LeftRest || b == LeftRest) {
        LeftRest = LeftRest - b;
        lsb = 1;
      }
      mpz_base_class::LeftShift3(Quotient, lsb);
      //    std::cout << "Quotient=" << Quotient << std::endl;
      n--;
    }
    q = Quotient;
    r = LeftRest;
  }
 
  bool mpz_base_class::testBit(int n) {
    unsigned int test_byte = n / BIT;
    int test_mask = 1 << (n % BIT);
    if (test_byte >= this->n) return false;
    if ((this->b[test_byte] & test_mask) > 0) return true;
    return false;
  }
 
/*----------------------------------------------*/
  mpz_class::mpz_class() {
//    std::cout << "mpz_class constructor1" << std::endl;
    this->base = mpz_base_class();
    this->negative = false;
  }
 
  mpz_class::~mpz_class() {
//    std::cout << "mpz_class destructor1" << std::endl;
    this->negative = false;
  }
 
  mpz_class::mpz_class(const signed long c) {
//    std::cout << "mpz_class costructor2" << std::endl;
    if (c >= 0) {
      this->base = mpz_base_class(c);
      this->negative = false;
    } else {
      this->base = mpz_base_class(-c);
      this->negative = true;
    }
  }
 
  mpz_class::mpz_class(const mpz_class &ob) {
//    std::cout << "mpz_class constructor3" << std::endl;
    this->base = ob.base;
    this->negative = ob.negative;
  }
 
  mpz_class &mpz_class::operator=(mpz_class const &ob) {
//    std::cout << "mpz_class operator=(mpz_class&)" << std::endl;
    this->base = ob.base;
    this->negative = ob.negative;
    return *this;
  }
 
//  mpz_class &mpz_class::operator=(mpz_base_class const &ob) {
//   std::cout << "mpz_class operator=(mpz_base_class&)" << std::endl;
//    this->mpz_base_class::operator=(ob);
//    this->negative = false;
//    return *this;
//  }
 
//  bool operator==(mpz_class const &a, mpz_class const &b) {
//    std::cout << "mpz_class::operator==" << std::endl;
//    if (a.negative == b.negative)
//      return operator==(a.base, b.base);
//    return false;
//  }
 
  std::ostream &operator<<(std::ostream &stream, mpz_class c) {
    if (c.negative)
      stream << '-';
    return operator<<(stream, c.base);
  }
 
  mpz_class operator+(mpz_class const &a, mpz_class const &b) {
    mpz_class r;
    if (!a.negative && !b.negative) {
      r.base = a.base + b.base; /* old.comment: operator=(mpz_class, mpz_base_class) */
      r.negative = false;
    } else if (a.negative && !b.negative) {
      mpz_class t = -a; assert(t.negative == false);
      if (t.base < b.base) { /* t < b */
        r.base = b.base - t.base;
        r.negative = false;
      } else { /* b < t */
        r.base = t.base - b.base;
        r.negative = true;
      }
      if (mpz_base_class::iszero(r.base))
        r.negative = false;
    } else if (!a.negative && b.negative) {
      mpz_class t = -b; assert(t.negative == false);
      if (operator<(t.base, a.base) == true) { /* t < a */
        r.base = a.base - t.base;
        r.negative = false;
      } else { /* a < t */
        r.base = t.base - a.base;
        r.negative = true;
      }
      if (mpz_base_class::iszero(r.base))
        r.negative = false;
    } else if (a.negative && b.negative) {      
      QZ::mpz_class aa = a, bb = b;
      aa = -aa; bb = -bb;
      r.base = aa.base + bb.base;
      r.negative = true;
      if (mpz_base_class::iszero(r.base))
        r.negative = false;
    }
    return r;
  }
 
  mpz_class operator-(mpz_class const &a, mpz_class const &b) {
    QZ::mpz_class r = -b;
    return a + r;
  }
 
  bool operator<(mpz_class const &a, mpz_class const &b) {
    QZ::mpz_class r = a - b;
    if (r.negative)
      return true;
    return false;
  }
 
  mpz_class operator*(mpz_class const &a, mpz_class const &b) {
    mpz_class x = (a > 0) ? a : -a;
    mpz_class y = (b > 0) ? b : -b;
    assert(x >= 0 && y >= 0);
    mpz_class r;
    r.base = x.base * y.base;
 
    if (a >= 0 && b >= 0)  {
    } else if (a < 0 && b >= 0) {
      r = -r;
    } else if (a >= 0 && b < 0) {
      r = -r;
    } if (a < 0 && b < 0) {
    }
    if (mpz_base_class::iszero(r.base)) r.negative = false;
    return r;
  }
 
  mpz_class operator/(mpz_class const &a, mpz_class const &b) {
    mpz_class x = (a >= 0) ? a : -a;
    mpz_class y = (b >= 0) ? b : -b;
    mpz_class q, r;
    mpz_base_class::div2(x.base, y.base, q.base, r.base);
    if (a >= 0 && b >= 0) {
    } else if (a < 0 && b >= 0) {
      q = -q; r = -r;
      if (mpz_base_class::iszero(q.base)) q.negative = false;
      if (mpz_base_class::iszero(r.base)) r.negative = false;
    } else if (a >= 0 && b < 0) {
      q = -q;
      if (mpz_base_class::iszero(q.base)) q.negative = false;
      if (mpz_base_class::iszero(r.base)) r.negative = false;
    } else if (a < 0 && b < 0) {
      r = -r;
      if (mpz_base_class::iszero(q.base)) q.negative = false;
      if (mpz_base_class::iszero(r.base)) q.negative = false;
    }
    return q;
  }
 
  mpz_class operator%(mpz_class const &a, mpz_class const &b) {
    mpz_class x = (a >= 0) ? a : -a;
    mpz_class y = (b >= 0) ? b : -b;
    mpz_class q, r;
    mpz_base_class::div2(x.base, y.base, q.base, r.base);
    if (a >= 0 && b >= 0) {
    } else if (a < 0 && b >= 0) {
      q = -q; r = -r;
      if (mpz_base_class::iszero(q.base)) q.negative = false;
      if (mpz_base_class::iszero(r.base)) r.negative = false;
    } else if (a >= 0 && b < 0) {
      q = -q;
      if (mpz_base_class::iszero(q.base)) q.negative = false;
      if (mpz_base_class::iszero(r.base)) r.negative = false;
    } else if (a < 0 && b < 0) {
      r = -r;
      if (mpz_base_class::iszero(q.base)) q.negative = false;
      if (mpz_base_class::iszero(r.base)) r.negative = false;
    }
    return r;
  }
 
  int mpz_base_class::bitLength() {
    if (this->n == 0)
      return 0;
 
    int n = this->n;
    int i;
    for (i = n - 1; !(b[i] > 0); --i) {}
 
    CONTAINER msb = this->b[i];
 
    int j = 0;
    while (msb > 0) {
      j++;
      msb = msb >> 1;
    }
    return BIT * i + j;
  }
 
  int mpz_class::bitLength() {
    return this->base.bitLength();
  }
 
} /* namespace QZ */
 
bool test00() {
  std::cout << "test00" << std::endl;
  return true;
}
bool test01() {
  /* constructor1, destructor */
  std::cout << "test01" << std::endl;
  QZ::mpz_base_class a;
  a.dump();
  if (a.get_mpzclass_n() != 0) return false;
  if (a.get_mpzclass_b() != 0) return false;
  return true;
}
 
bool test02() {
  /* constructor2 */
  std::cout << "test02" << std::endl;
  std::cout << "test02:0" << std::endl;
  QZ::mpz_base_class a(0);
  a.dump();
  if (a.get_mpzclass_n() != 1) return false;
  if (*a.get_mpzclass_b() != 0) return false;
 
  std::cout << "test02:1" << std::endl;
  QZ::mpz_base_class b(1);
  b.dump();
  if (b.get_mpzclass_n() != 1) return false;
  if (*b.get_mpzclass_b() != 1) return false;
 
  std::cout << "test02:2" << std::endl;
  QZ::mpz_base_class c(2);
  c.dump();
  if (c.get_mpzclass_n() != 1) return false;
  if (*c.get_mpzclass_b() != 2) return false;
 
  std::cout << "test02:4" << std::endl;
  QZ::mpz_base_class d(4);
  d.dump();
  if (d.get_mpzclass_n() != 1) return false;
  if (*d.get_mpzclass_b() != 4) return false;
 
  std::cout << "test02:8" << std::endl;
  QZ::mpz_base_class e(8);
  e.dump();
  if (e.get_mpzclass_n() != 2) return false;
  if (*e.get_mpzclass_b() != 0) return false;
  if (*(e.get_mpzclass_b() + 1) != 1) return false;
 
  std::cout << "test02:10" << std::endl;
  QZ::mpz_base_class f(10);
  f.dump();
  if (f.get_mpzclass_n() != 2) return false;
  if (*f.get_mpzclass_b() != 2) return false;
  if (*(f.get_mpzclass_b() + 1) != 1) return false;
 
  std::cout << "test02:16" << std::endl;
  QZ::mpz_base_class g(16);
  g.dump();
  if (g.get_mpzclass_n() != 2) return false;
  if (*g.get_mpzclass_b() != 0) return false;
  if (*(g.get_mpzclass_b() + 1) != 2) return false;
 
  std::cout << "test02:32" << std::endl;
  QZ::mpz_base_class h(32);
  h.dump();  
  if (h.get_mpzclass_n() != 2) return false;
  if (*h.get_mpzclass_b() != 0) return false;
  if (*(h.get_mpzclass_b() + 1) != 4) return false;
 
  std::cout << "test02:64" << std::endl;
  QZ::mpz_base_class i(64);
  i.dump();  
  if (i.get_mpzclass_n() != 3) return false;
  if (*i.get_mpzclass_b() != 0) return false;
  if (*(i.get_mpzclass_b() + 1) != 0) return false;
  if (*(i.get_mpzclass_b() + 2) != 1) return false;
  return true;
}
 
bool test03() {
  /* constructor3 */
  std::cout << "test03" << std::endl;
  QZ::mpz_base_class a;
  QZ::mpz_base_class b = a;
  b.dump();
  if (b.get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_b() != 0) return false;
  QZ::mpz_base_class c = 1;
  QZ::mpz_base_class d = c;
  d.dump();
  if (d.get_mpzclass_n() != 1) return false;
  if (*d.get_mpzclass_b() != 1) return false;
  return true;
}
 
bool test04() {
  /* operator= */
  std::cout << "test04" << std::endl;
  QZ::mpz_base_class a;
  QZ::mpz_base_class b;
  b = a;
  a.dump();
  b.dump();
  if (b.get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_b() != 0) return false;
  QZ::mpz_base_class c = 1;
  c.dump();
  QZ::mpz_base_class d;
  d = c;
  d.dump();  
  if (d.get_mpzclass_n() != 1) return false;
  if (*d.get_mpzclass_b() != 1) return false;
  return true;
}
 
bool test05() {
  /* operator== */
  std::cout << "test05" << std::endl;
  QZ::mpz_base_class a = 1;
  QZ::mpz_base_class b = 1;
  if (!(a == b)) return false;
  QZ::mpz_base_class x = 100;
  QZ::mpz_base_class y = 100;
  if (!(x == y)) return false;  
  QZ::mpz_base_class u;
  QZ::mpz_base_class v;
  if (!(u == v)) return false;  
  QZ::mpz_base_class w = 0;
  if (!(u == w)) return false;  
  return true;
}
 
bool test06() {
  /* operator==, operator!= */
  std::cout << "test06" << std::endl;
  QZ::mpz_base_class a = 0;
  QZ::mpz_base_class b = 1;
  QZ::mpz_base_class c = 1;
  if (!(a != b)) return false;
  if (b != c) return false;
  if (a == b) return false;
  if (!(b == c)) return false;
  return true;
}
 
/*---------------------------------------------------------*/
 
bool test23() {
  /* addition sign flag to mpz_class */
  /* constructor1 */
  std::cout << "test23" << std::endl;
  QZ::mpz_class x;
  x.dump();
  if (x.get_mpzclass_base().get_mpzclass_n() != 0) return false;
  if (x.get_mpzclass_base().get_mpzclass_b() != 0) return false;
  if (x.get_mpzclass_negative() != 0) return false;
 
  return true;
}
 
bool test24() {
  std::cout << "test24" << std::endl;
  QZ::mpz_class a1(0);
  a1.dump();
  if (a1.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*a1.get_mpzclass_base().get_mpzclass_b() != 0) return false;
  if (a1.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a2(1);
  a2.dump();
  if (a2.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*a2.get_mpzclass_base().get_mpzclass_b() != 1) return false;
  if (a2.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a3(2);
  a3.dump();
  if (a3.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*a3.get_mpzclass_base().get_mpzclass_b() != 2) return false;
  if (a3.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a4(4);
  a4.dump();
  if (a4.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*a4.get_mpzclass_base().get_mpzclass_b() != 4) return false;
  if (a4.get_mpzclass_negative() != 0) return false;
  QZ::mpz_class a5(8);
  a5.dump();
  if (a5.get_mpzclass_base().get_mpzclass_n() != 2) return false;
  if (*a5.get_mpzclass_base().get_mpzclass_b() != 0) return false;
  if (*(a5.get_mpzclass_base().get_mpzclass_b() + 1) != 1) return false;
  if (a5.get_mpzclass_negative() != 0) return false;
 
  std::cout << "test24:-1" << std::endl;
  QZ::mpz_class a6(-1);
  a6.dump();
  if (a6.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*a6.get_mpzclass_base().get_mpzclass_b() != 1) return false;
  if (a6.get_mpzclass_negative() != 1) return false;
 
  std::cout << "test24:-2" << std::endl;
  QZ::mpz_class a7(-2);
  a7.dump();
  if (a7.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*a7.get_mpzclass_base().get_mpzclass_b() != 2) return false;
  if (a7.get_mpzclass_negative() != 1) return false;
 
  std::cout << "test24:-4" << std::endl;
  QZ::mpz_class a8(-4);
  a8.dump();
  if (a8.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*a8.get_mpzclass_base().get_mpzclass_b() != 4) return false;
  if (a8.get_mpzclass_negative() != 1) return false;
 
  std::cout << "test24:-8" << std::endl;
  QZ::mpz_class a9(-8);
  a9.dump();
  if (a9.get_mpzclass_base().get_mpzclass_n() != 2) return false;
  if (*a9.get_mpzclass_base().get_mpzclass_b() != 0) return false;
  if (*(a9.get_mpzclass_base().get_mpzclass_b() + 1) != 1) return false;
  if (a9.get_mpzclass_negative() != 1) return false;
 
  return true;
}
 
bool test25() {
  std::cout << "test25" << std::endl;
  QZ::mpz_class a;
  QZ::mpz_class b = a;
  b.dump();
  if (b.get_mpzclass_base().get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_base().get_mpzclass_b() != 0) return false;
  if (b.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class c = 8;
  QZ::mpz_class d = c;
  d.dump();
  if (d.get_mpzclass_base().get_mpzclass_n() != 2) return false;
  if (*(d.get_mpzclass_base().get_mpzclass_b()) != 0) return false;
  if (*(d.get_mpzclass_base().get_mpzclass_b() + 1) != 1) return false;
  if (b.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class e = -8;
  QZ::mpz_class f = e;
  f.dump();
  if (f.get_mpzclass_base().get_mpzclass_n() != 2) return false;
  if (*f.get_mpzclass_base().get_mpzclass_b() != 0) return false;
  if (*(f.get_mpzclass_base().get_mpzclass_b() + 1) != 1) return false;
  if (f.get_mpzclass_negative() != 1) return false;
 
  return true;
}
 
bool test26() {
  std::cout << "test26" << std::endl;
 
  QZ::mpz_class a;
  QZ::mpz_class b;
  b = a;
  a.dump();
  b.dump();
  if (b.get_mpzclass_base().get_mpzclass_n() != 0) return false;
  if (b.get_mpzclass_base().get_mpzclass_b() != 0) return false;
  if (b.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class c = 1;
  c.dump();
  QZ::mpz_class d;
  d = c;
  d.dump();  
  if (d.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*(d.get_mpzclass_base().get_mpzclass_b()) != 1) return false;
  if (d.get_mpzclass_negative() != 0) return false;
 
  QZ::mpz_class e = -1;
  e.dump();
  QZ::mpz_class f;
  f = e;
  f.dump();  
  if (f.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*(f.get_mpzclass_base().get_mpzclass_b()) != 1) return false;
  if (f.get_mpzclass_negative() != 1) return false;
 
  return true;
}
 
bool test27() {
  std::cout << "test27:1" << std::endl;
  QZ::mpz_class a = 1;
  QZ::mpz_class b = 1;
  if (!(a == b)) return false;
 
  std::cout << "test27:100" << std::endl;
  QZ::mpz_class x = 100;
  QZ::mpz_class y = 100;
  if (!(x == y)) return false;  
 
  std::cout << "test27:0" << std::endl;
  QZ::mpz_class u;
  QZ::mpz_class v;
  if (!(u == v)) return false;  
  QZ::mpz_class w = 0;
  if (!(u == w)) return false;  
 
  std::cout << "test27:-100" << std::endl;
  QZ::mpz_class i = -100;
  QZ::mpz_class j = -100;
  if (!(i == j)) return false;  
  QZ::mpz_class k = 100;
  if (i == k) return false;  
 
  return true;
}
 
bool test28() {
  std::cout << "test28" << std::endl;
  QZ::mpz_class a = 0;
  QZ::mpz_class b = -1;
  QZ::mpz_class c = -1;
 
  if (!(a != b)) return false;
  if (b != c) return false;
  if (a == b) return false;
  if (!(b == c)) return false;
 
  return true;
}
 
bool test29() {
  /* operator-() */
  std::cout << "test29" << std::endl;
  QZ::mpz_class x = 1;
  QZ::mpz_class y = -x;
  if (y != -1) return false;
  x = QZ::mpz_class(-1);
  y = -x;
  if (y != 1) return false;
  return true;
}
 
bool test30() {
  std::cout << "test30" << std::endl;
  QZ::mpz_class x = -1;
  std::cout << "x = " << x << std::endl;
  x = -x;
  std::cout << "x = " << x << std::endl;
  if (x.get_mpzclass_base().get_mpzclass_n() != 1) return false;
  if (*(x.get_mpzclass_base().get_mpzclass_b()) != 1) return false;
  if (x.get_mpzclass_negative() != false) return false;
 
  QZ::mpz_class y = -100;
  std::cout << "y = " << y << std::endl;
  y = -y;
  std::cout << "y = " << y << std::endl;
  if (x.get_mpzclass_negative() != false) return false;
 
  return true;
}
 
bool test31() {
  std::cout << "test31" << std::endl;
  std::cout << "3+5=8" << std::endl;
  QZ::mpz_class a = 3;
  QZ::mpz_class b = 5;
  QZ::mpz_class c = 8;
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "-3+(-5)=-8" << std::endl;
  a = QZ::mpz_class(-3);
  b = QZ::mpz_class(-5);
  c = QZ::mpz_class(-8);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "-3+5=2" << std::endl;
  a = QZ::mpz_class(-3);
  b = QZ::mpz_class(5);
  c = QZ::mpz_class(2);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "-3+1=-2" << std::endl;
  a = QZ::mpz_class(-3);
  b = QZ::mpz_class(1);
  c = QZ::mpz_class(-2);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "5+(-3)=+2" << std::endl;
  a = QZ::mpz_class(5);
  b = QZ::mpz_class(-3);
  c = QZ::mpz_class(2);
  if (a + b != c) return false;
  std::cout << "-------------" << std::endl;
  std::cout << "5+(-8)=-3" << std::endl;
  a = QZ::mpz_class(5);
  b = QZ::mpz_class(-8);
  c = QZ::mpz_class(-3);
  if (a + b != c) return false;  
  std::cout << "-------------" << std::endl;
  return true;
}
 
bool test32() {
  std::cout << "test32" << std::endl;
  for (int i = -10; i <= +10; i++) {
    for (int j = -10; j <= +10; j++) {
      QZ::mpz_class z1 = i + j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
      QZ::mpz_class z2 = x + y;
//      std::cout << "z1 = " << i + j << std::endl;
      if (z1 != z2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
 
bool test33() {
  std::cout << "test33" << std::endl;
  for (int i = -10; i <= +10; i++) {
    for (int j = -10; j <= +10; j++) {
      QZ::mpz_class z1 = i - j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
      QZ::mpz_class z2 = x - y;
//      std::cout << "z1 = " << i - j << std::endl;
      if (z1 != z2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
bool test34() {
  std::cout << "test34" << std::endl;
  for (int i = -10; i <= 10; i++) {
    for (int j = -10; j <= 10; j++) {
      QZ::mpz_class x = i;
      QZ::mpz_class y = j;
 
//      std::cout << "i=" << i << ",j=" << j << ",x=" << x << ",y=" << y << std::endl;      
//      std::cout << i << "==" << j << ": " << (i==j) << std::endl;
//      std::cout << x << "==" << y << ": " << (x==y) << std::endl;
      if ((i == j) ^ (x == j)) { std::cout << "i==j" << std::endl; return false; }
 
//      std::cout << i << "!=" << j << ": " << (i!=j) << std::endl;
//      std::cout << x << "!=" << y << ": " << (x!=y) << std::endl;
      if ((i != j) ^ (x != y)) { std::cout << "i!=j" << std::endl; return false; }
 
      if ((i < j) ^ (x < y))   { std::cout << "i<j" << std::endl; return false; }
      if ((i <= j) ^ (x <= y)) { std::cout << "i<=j" << std::endl; return false; }
      if ((i > j) ^ (x > y))   { std::cout << "i>j" << std::endl; return false; }
      if ((i >= j) ^ (x >= y)) { std::cout << "i>=j" << std::endl; return false; }
    }
  }
  return true;
}
 
bool test35() {
  std::cout << "test35" << std::endl;
  for (int i = -10; i <= +10; i++) {
    for (int j = -10; j <= +10; j++) {
//      std::cout << "i = " << i << ", j = " << j << std::endl;
      QZ::mpz_class z1 = i * j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
//      std::cout << "z1 = " << i * j << std::endl;
      QZ::mpz_class z2 = x * y;
//      std::cout << "z2 = " << z2 << std::endl;
 
      if (z1 != z2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
 
int seed = 31415926;
int const n11 = 1000;
bool test36() {
  std::cout << "test36" << std::endl;
  srand(seed);
  for (int i = 0; i < n11; i++) {
    int a, b;
    a = (rand() >> 16);
    b = (rand() >> 16);
    if (rand() % 2 == 1) a = -a;
    if (rand() % 2 == 1) b = -b;
    QZ::mpz_class x(a);
    QZ::mpz_class y(b);
    QZ::mpz_class z = x * y;
    // std::cout << "x = " << x << std::endl;
 
    if (z != a * b) {
      std::cout << "i = " << i << std::endl;
      std::cout << "NOT EQUAL: x = " << x << ", y = " << y << ", a = " << a << ", b = " << b << ", a * b = " << a * b << std::endl;
      std::cout << "z = " << z << std::endl;
      z.dump();
      return false;
    }
  }
  return true;
}
 
int const n12 = 50;
bool test37() {
  std::cout << "test37" << std::endl;
  for (int i = -n12; i <= +n12; i++) {
    for (int j = -n12; j <= +n12; j++) {
//      std::cout << "i = " << i << ", j = " << j << std::endl;
      if (j == 0) continue;
      QZ::mpz_class q1 = i / j;
      QZ::mpz_class r1 = i % j;
      QZ::mpz_class x(i);
      QZ::mpz_class y(j);      
//      std::cout << "q1 = " << i / j << std::endl;
      QZ::mpz_class q2 = x / y;
//      std::cout << "q2 = " << q2 << std::endl;
//      std::cout << "r1 = " << i % j << std::endl;
      QZ::mpz_class r2 = x % y;
//      std::cout << "r2 = " << r2 << std::endl;
 
      if (q1 != q2 || r1 != r2) {
        std:: cout << "i = " << i << ", j = " << j << std::endl;
        std:: cout << "not equal!!" << std::endl;
        return false;
      }
    }
  }
  return true;
}
 
int const n14 = 1000;
bool test38() {
  std::cout << "test38" << std::endl;
  srand(seed);
  for (int i = 0; i < n14; i++) {
    QZ::mpz_class x(rand());
    QZ::mpz_class y(rand());
    if (rand() % 2 == 1) x = -x;
    if (rand() % 2 == 1) y = -y;
//    std::cout << "x = " << x << std::endl;
    QZ::mpz_class q = x / y;
    QZ::mpz_class r = x % y;
    if (!(q * y + r == x)) {
      std::cout << "x = " << x << ",y = " << y << ",q = " << q << ",r = " << r << std::endl;
      std::cout << "q * y = " << q * y << std::endl;
      std::cout << "q * y + r = " << q * y + r << std::endl;
      std::cout << "x =         " << q * y + r << std::endl;
      std::cout << "not equal!" << std::endl;
      return false;
    }
  }
  return true;
}
 
bool test39() {
  std::cout << "test39" << std::endl;
  QZ::mpz_class t = 2;
  QZ::mpz_class s = 3;
  t += s;
  std::cout << "t = " << t << std::endl;
  if (t != 5) return false;
 
  int n = 5;
  int d = 7;
  t = QZ::mpz_class(5);
  for (; n < 100; n += d, t += d) {
    std::cout << "n = " << n << ", t = " << t << std::endl;
    if (n != t) {
      std::cout << "n = " << n << ", t = " << t << std::endl;
      return false;
    }
  }
 
  return true;
}
 
bool test40() {
  std::cout << "test40A" << std::endl;
  QZ::mpz_base_class a = 2;
  a = a << 1;
  std::cout << "a = " << a << std::endl;
  a.dump();
  if (a != 4) return false;
 
  QZ::mpz_base_class b = 2;
  b = b >> 1;
  std::cout << "b = " << b << std::endl;
  b.dump();
  if (b != 1) return false;
 
  int m = 3;
  QZ::mpz_base_class M = m;
  for (int n = 0; n < 8; n++) {
    std::cout << "n = " << n << std::endl;
    std::cout << "m << " << n << " = " << (m << n) << std::endl;
    std::cout << "M << " << n << " = " << (M << n) << std::endl;
    if ((m << n) != (M << n)) return false;
  }
 
  m = 1024;
  M = m;
  for (int n = 0; n < 8; n++) {
    std::cout << "n = " << n << std::endl;
    std::cout << "m >> " << n << " = " << (m >> n) << std::endl;
    std::cout << "M >> " << n << " = " << (M >> n) << std::endl;
    if ((m >> n) != (M >> n)) return false;
  }
 
  QZ::mpz_base_class c = 3;
  std::cout << "c = " << c << std::endl; // 3
  c <<= 1;
  std::cout << "c = " << c << std::endl; //6
  if (c != 6) return false;
  c <<= 1;
  std::cout << "c = " << c << std::endl; //12
  if (c != 12) return false;
  c <<= 1;
  std::cout << "c = " << c << std::endl;//24
  if (c != 24) return false;
 
  c = 1024;
  std::cout << "c = " << c << std::endl; // 1024
  c >>= 1;
  std::cout << "c = " << c << std::endl; // 512
  if (c != 512) return false;
  c >>= 1;
  std::cout << "c = " << c << std::endl; // 256
  if (c != 256) return false;
  c >>= 1;
  std::cout << "c = " << c << std::endl;//128
  if (c != 128) return false;
 
  /* ---------------- */
  std::cout << std::endl << "test40B" << std::endl;
 
  QZ::mpz_class x = 2;
  std::cout << "x = " << x << std::endl;
  x = x << 1;
  std::cout << "x = " << x << std::endl;
  x.dump();
  if (x != 4) return false;
 
  QZ::mpz_base_class y = 2;
  std::cout << "y = " << y << std::endl;
  y = y >> 1;
  std::cout << "y = " << y << std::endl;
  y.dump();
  if (y != 1) return false;
 
  int z = 3;
  QZ::mpz_base_class Z = z;
  for (int n = 0; n < 8; n++) {
    std::cout << "n = " << n << std::endl;
    std::cout << "z << " << n << " = " << (z << n) << std::endl;
    std::cout << "Z << " << n << " = " << (Z << n) << std::endl;
    if ((z << n) != (Z << n)) return false;
  }
 
  z = 1024;
  Z = m;
  for (int n = 0; n < 8; n++) {
    std::cout << "n = " << n << std::endl;
    std::cout << "z >> " << n << " = " << (z >> n) << std::endl;
    std::cout << "Z >> " << n << " = " << (Z >> n) << std::endl;
    if ((z >> n) != (Z >> n)) return false;
  }
 
  QZ::mpz_class w = 3;
  std::cout << "w = " << w << std::endl; // 3
  w <<= 1;
  std::cout << "w = " << w << std::endl; //6
  if (w != 6) return false;
  w <<= 1;
  std::cout << "w = " << w << std::endl; //12
  if (w != 12) return false;
  w <<= 1;
  std::cout << "w = " << w << std::endl;//24
  if (w != 24) return false;
 
  w = 1024;
  std::cout << "w = " << w << std::endl; // 1024
  w >>= 1;
  std::cout << "w = " << w << std::endl; // 512
  if (w != 512) return false;
  w >>= 1;
  std::cout << "w = " << w << std::endl; // 256
  if (w != 256) return false;
  w >>= 1;
  std::cout << "w = " << w << std::endl;//128
  if (w != 128) return false;
 
  std::cout << std::endl << "test40C" << std::endl;
 
  int n = 1;
  QZ::mpz_class t = 1;
  for (int i = 0; i < 10; i++) {
    int m = n << i;
    QZ::mpz_class s = t << i;
    std::cout << "i = " << i << ", m = " << m << ", s = " << s << std::endl;
    std::cout << "s: "; s.dump();
    if (m != s) {
      std::cout << "bad!" << std::endl;
      return false;
    }
  }
 
  n = 0x1000;
  t = QZ::mpz_class(n);
  for (int i = 0; i < 10; i++) {
    int m = n >> i;
    QZ::mpz_class s = t >> i;
    std::cout << "i = " << i << ", m = " << m << ", s = " << s << std::endl;
    if (m != s) {
      std::cout << "bad!" << std::endl;
      return false;
    }
  }
  return true;
}
 
bool test41() {
  std::cout << "test41" << std::endl;
  QZ::mpz_class n;
  int m;
  n = QZ::mpz_class(1);
  m = n.bitLength();
  if (m != 1) return false;
  n = QZ::mpz_class(2);
  m = n.bitLength();
  if (m != 2) return false;
  n = QZ::mpz_class(3);
  m = n.bitLength();
  if (m != 2) return false;
  n = QZ::mpz_class(4);
  m = n.bitLength();
  if (m != 3) return false;
  n = QZ::mpz_class(8);
  m = n.bitLength();
  if (m != 4) return false;
  n = QZ::mpz_class(16);
  m = n.bitLength();
  if (m != 5) return false;
  n = QZ::mpz_class(32);
  m = n.bitLength();
  if (m != 6) return false;
  n = QZ::mpz_class(64);
  m = n.bitLength();
  if (m != 7) return false;
  n = QZ::mpz_class(128);
  m = n.bitLength();
  if (m != 8) return false;
  n = QZ::mpz_class(256);
  m = n.bitLength();
  if (m != 9) return false;
  return true;
}
 
bool test42() {
  std::cout << "test42" << std::endl;
  QZ::mpz_base_class r(4 + 256);
  r.test42();
  int m = r.bitLength();
  std::cout << "r = " << r << std::endl;
  std::cout << "m = " << m << std::endl;
  if (m != 3) return false;
  return true;
}
 
bool test43() {// 2018/8/25
  std::cout << "test43" << std::endl;
 
  QZ::mpz_base_class a = 5, b;
  b = a++;
  std::cout << "a = " << a << std::endl;
  std::cout << "b = " << b << std::endl;
  if (a != 6) return false;
  if (b != 5) return false;
 
  QZ::mpz_class A = 7, B;
  B = A++;
  std::cout << "A = " << A << std::endl;
  std::cout << "B = " << B << std::endl;
  if (A != 8) return false;
  if (B != 7) return false;
 
  QZ::mpz_class x = -1;
  x++;
  std::cout << "x = " << x << std::endl;  
  if (x != 0) return false;
 
  QZ::mpz_base_class k, K;
  QZ::mpz_class d, D;
  k = K = 35; d = D = 68;
  for (int n = 0; n < 100; n++) {
    k++;
    d++;
    if (k != K + n + 1) return false;
    if (d != D + n + 1) return false;    
  }
  return true;
}
 
bool test44() {// 2018/8/25
  std::cout << "test44" << std::endl;
 
  QZ::mpz_base_class a = 5, b;
  b = a--;
  std::cout << "a = " << a << std::endl;
  std::cout << "b = " << b << std::endl;
  if (a != 4) return false;
  if (b != 5) return false;
 
  QZ::mpz_class A = 7, B;
  B = A--;
  std::cout << "A = " << A << std::endl;
  std::cout << "B = " << B << std::endl;
  if (A != 6) return false;
  if (B != 7) return false;
 
  QZ::mpz_class x = 0;
  x--;
  std::cout << "x = " << x << std::endl;  
  x.dump();
  if (x != -1) return false;
  std::cout << "test44 continue." << std::endl;
 
  QZ::mpz_base_class k, K;
  QZ::mpz_class d, D;
  k = K = 135; d = D = 48;
  for (int n = 0; n < 100; n++) {
    k--;
    d--;
    if (k != K - n - 1) return false;
    if (d != D - n - 1) return false;    
  }
 
//  QZ::mpz_base_class p = 0;
//  p--;
//  std::cout << "p = " << p << std::endl; // p = -1
//  p.dump();
 
  return true;
}
 
bool test45() {// 2018/8/25
  std::cout << "test45" << std::endl;
 
  QZ::mpz_base_class a = 5, b;
  b = ++a;
  std::cout << "a = " << a << std::endl;
  std::cout << "b = " << b << std::endl;
  if (a != 6) return false;
  if (b != 6) return false;
 
  QZ::mpz_class A = 7, B;
  B = ++A;
  std::cout << "A = " << A << std::endl;
  std::cout << "B = " << B << std::endl;
  if (A != 8) return false;
  if (B != 8) return false;
 
  QZ::mpz_class x = -1;
  ++x;
  std::cout << "x = " << x << std::endl;  
  if (x != 0) return false;
 
  QZ::mpz_base_class k, K;
  QZ::mpz_class d, D;
  k = K = 35; d = D = 68;
  for (int n = 0; n < 100; n++) {
    ++k;
    ++d;
    if (k != K + n + 1) return false;
    if (d != D + n + 1) return false;    
  }
 
  std::cout << "test45 continue." << std::endl;
 
  a = 5;
  b = --a;
  std::cout << "a = " << a << std::endl;
  std::cout << "b = " << b << std::endl;
  if (a != 4) return false;
  if (b != 4) return false;
 
  A = 7;
  B = --A;
  std::cout << "A = " << A << std::endl;
  std::cout << "B = " << B << std::endl;
  if (A != 6) return false;
  if (B != 6) return false;
 
  x = 0;
  --x;
  std::cout << "x = " << x << std::endl;  
  x.dump();
  if (x != -1) return false;
 
  k = K = 135; d = D = 48;
  for (int n = 0; n < 100; n++) {
    std::cout << "n = " << n << std::endl;
    --k;
    --d;
    if (k != K - n - 1) return false;
    if (d != D - n - 1) return false;    
  }
 
  return true;
}
 
bool test46() {// 2018/8/25
  std::cout << "test46" << std::endl;
  QZ::mpz_base_class x = 1;
  bool b;
  b = !x;
  if (b != false) return false;
  x = 0;
  b = !x;
  if (b != true) return false;
  return true;
}
 
bool test47() {
  std::cout << "test47" << std::endl;
  QZ::mpz_base_class x = 5;
  if ((+x) != 5) return false;
  QZ::mpz_class y = 3;
  if ((+y) != 3) return false;
  if ((-y) != -3) return false;
  y = -8;
  if ((+y) != -8) return false;
  if ((-y) != 8) return false;
  /* generalize -> abbrev. */
 
  return true;
}
 
bool test48() { /* bool() */
  std::cout << "test48" << std::endl;
  QZ::mpz_base_class x = 5;
  if (x) ; else return false;
  x = 0;
  if (x) return false;
 
  QZ::mpz_class y = 5;  
  if (y) ; else return false;
  y = 0;
  if (y) return false;
  /* generalize -> abbrev. */  
 
  return true;
}
 
bool test49() {
  std::cout << "test49" << std::endl;
  int a = 123, b = 45;
  QZ::mpz_base_class x, y;
/*              *                 *                             * */
  x = a; y = (x += b); if (x != a + b) return false; if (y != a + b) return false;  
  x = a; y = (x -= b); if (x != a - b) return false; if (y != a - b) return false;  
  x = a; y = (x *= b); if (x != a * b) return false; if (y != a * b) return false;  
  x = a; y = (x /= b); if (x != a / b) return false; if (y != a / b) return false;  
  x = a; y = (x %= b); if (x != a % b) return false; if (y != a % b) return false;  
  return true;
}
 
bool test50() {
  std::cout << "test50" << std::endl;
  int a = 123, b = 45;
  QZ::mpz_class x, y;
/*              *                 *                             * */
  x = a; y = (x += b); if (x != a + b) return false; if (y != a + b) return false;  
  x = a; y = (x -= b); if (x != a - b) return false; if (y != a - b) return false;  
  x = a; y = (x *= b); if (x != a * b) return false; if (y != a * b) return false;  
  x = a; y = (x /= b); if (x != a / b) return false; if (y != a / b) return false;  
  x = a; y = (x %= b); if (x != a % b) return false; if (y != a % b) return false;  
  return true;
}
 
void test() {
  if (test00() == true) std::cout << "00 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test01() == true) std::cout << "01 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test02() == true) std::cout << "02 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test03() == true) std::cout << "03 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test04() == true) std::cout << "04 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test05() == true) std::cout << "05 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test06() == true) std::cout << "06 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test07() == true) std::cout << "07 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test08() == true) std::cout << "08 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test09() == true) std::cout << "09 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test10() == true) std::cout << "10 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test11() == true) std::cout << "11 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test12() == true) std::cout << "12 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test13() == true) std::cout << "13 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test14() == true) std::cout << "14 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test15() == true) std::cout << "15 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test16() == true) std::cout << "16 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test17() == true) std::cout << "17 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test18() == true) std::cout << "18 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test19() == true) std::cout << "19 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test20() == true) std::cout << "20 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test21() == true) std::cout << "21 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
//  if (test22() == true) std::cout << "22 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test23() == true) std::cout << "23 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test24() == true) std::cout << "24 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test25() == true) std::cout << "25 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test26() == true) std::cout << "26 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test27() == true) std::cout << "27 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test28() == true) std::cout << "28 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test29() == true) std::cout << "29 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test30() == true) std::cout << "30 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test31() == true) std::cout << "31 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test32() == true) std::cout << "32 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test33() == true) std::cout << "33 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test34() == true) std::cout << "34 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test35() == true) std::cout << "35 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test36() == true) std::cout << "36 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test37() == true) std::cout << "37 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test38() == true) std::cout << "38 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test39() == true) std::cout << "39 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test40() == true) std::cout << "40 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test41() == true) std::cout << "41 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test42() == true) std::cout << "42 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test43() == true) std::cout << "43 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test44() == true) std::cout << "44 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test45() == true) std::cout << "45 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test46() == true) std::cout << "46 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test47() == true) std::cout << "47 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test48() == true) std::cout << "48 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test49() == true) std::cout << "49 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  if (test50() == true) std::cout << "50 Complete.\n" << std::endl; else { std::cout << "***Error***" << std::endl; exit(0); }
  return;
}
 
int main() {
  test();
  return 0;
}
/* end */