Menu

Algorithms/Mathematics/Big Integer/Big Integer Class

Last-modified: 2008-05-23 (金) 10:48:22

Big Integer Class

多倍長整数クラス

GNU g++ Integer class

Outline

多倍長整数を表現するクラス.
やろうと思えばいくらでも演算子定義ができるが、
現実的にはこれくらいあれば困らない.
uvaでは必須.

Program 

/* #include <iostream>
 * #include <cstdio>
 *
 * _BIG_MAX 必要な桁数(あらかじめ4で割って余分な分を確保)
 */

class BigInteger {
private:
  short num[_BIG_MAX];
  int i;
  long carry, dd, rem;
public:
  bool operator=(long a) {
    for(i = 0 ; i < _BIG_MAX ; i++) {
      num[i] = a % 10000;
      a /= 10000;
    }

    return true;
  }

  BigInteger operator+(BigInteger a) {
    BigInteger temp;
    carry = 0;

    for(i = 0 ; i < _BIG_MAX ; i++) {
      dd = num[i] + a.num[i] + carry;
      temp.num[i] = dd % 10000;
      carry = dd / 10000;
    }

    return temp;
  }

  BigInteger operator+(int a) {
    BigInteger temp;
    carry = 0;

    for(i = 0 ; i < _BIG_MAX ; i++) {
      dd = num[i] + a + carry;
      temp.num[i] = dd % 10000;
      carry = dd / 10000;

      a /= 10000;
    }

    return temp;
  }

  // Result is positive
  BigInteger operator-(BigInteger a) {
    BigInteger temp;

    for(i = 0 ; i < _BIG_MAX - 1 ; i++) {
      if(num[i] < a.num[i]) {
        num[i + 1]--;
        num[i] += 10000;
      }

      temp.num[i] = num[i] - a.num[i];
    }

    return temp;
  }

  BigInteger operator*(long a) {
    BigInteger temp;
    carry = 0;

    for(i = 0 ; i < _BIG_MAX ; i++) {
      dd = num[i] * a + carry;
      temp.num[i] = dd % 10000;
      carry = dd / 10000;
    }

    return temp;
  }

  BigInteger operator/(long a) {
    BigInteger temp;
    rem = 0;

    for(i = 0 ; i < _BIG_MAX ; i++) {
      temp.num[i] = (num[i] + rem) / a;
      rem = ((num[i] + rem) % a) * 10000;
    }

    return temp;
  }

  long operator%(int a) {
    rem = 0;

    for(i = _BIG_MAX - 1 ; i >= 0 ; i--) {
      if(i == 0) {
        return (num[i] + rem) % a;
      }

      rem = ((num[i] + rem) % a) * 10000;
    }
  }

  BigInteger() {
    for(i = 0 ; i < _BIG_MAX ; i++) {
      num[i] = 0;
    }
  }

  void init(){
    for(i = 0 ; i < _BIG_MAX ; i++) {
      num[i] = 0;
    }
  }

  void print() {
    bool flag = false;

    for(i = _BIG_MAX - 1 ; i >= 0 ; i--) {
      if(flag) {
        printf("%04d", num[i]);
      } else if(num[i]) {
        printf("%d", num[i]);
        flag = true;
      } else if(i == 0) {
        cout << "0";
      }
    }
  }

  void println() {
    print();
    cout << endl;
  }
};