#include <iostream>
#include <string>
#include <cctype>
#include <cassert>
enum {
BIT = 3, // for test
// BIT = 30,
CMASK = 1 << BIT,
BMASK = CMASK - 1
};
class BigInteger {
private:
int n;
int *b;
private:
friend BigInteger sub(BigInteger const &a, BigInteger const &b, int &carry);
friend BigInteger mul1(BigInteger const &a, BigInteger const &b);
friend BigInteger mul2(BigInteger const &a, BigInteger const &b);
friend BigInteger div1(BigInteger const &a, BigInteger const &b, BigInteger &r);
friend void div2(BigInteger const &a, BigInteger const &b, BigInteger &q, BigInteger &r);
static bool iszero(BigInteger &n);
static void LeftShift(BigInteger &a);
static void RightShift(BigInteger &a, int &lsb);
static void LeftShift2(int &msb, BigInteger &a);
static void LeftShift3(BigInteger &a, int msb);
public:
BigInteger();
BigInteger(const BigInteger &ob);
BigInteger(const int n);
~BigInteger();
BigInteger &operator=(BigInteger n);
friend bool operator==(BigInteger const &a, BigInteger const &b);
friend bool operator!=(BigInteger const &a, BigInteger const &b);
friend BigInteger operator+(BigInteger const &a, BigInteger const &b);
friend BigInteger operator-(BigInteger const &a, BigInteger const &b);
friend BigInteger operator*(BigInteger const &a, BigInteger const &b);
friend BigInteger operator/(BigInteger const &a, BigInteger const &b);
friend BigInteger operator%(BigInteger const &a, BigInteger const &b);
friend bool operator<(BigInteger const &a, BigInteger const &b);
friend bool operator<=(BigInteger const &a, BigInteger const &b);
friend std::ostream &operator<<(std::ostream &stream, BigInteger c);
void dump() const {
std::cout << "n = " << this->n << ": ";
for (int i = 0; i < this->n; i++)
std::cout << i << ":" << this->b[i] << ",";
std::cout << std::endl;
}
};
BigInteger::BigInteger() {
this->n = 1;
this->b = new int[1];
this->b[0] = 0;
}
BigInteger::BigInteger(const BigInteger &ob) {
this->n = ob.n;
if (ob.n == 0) {
this->b = 0;
} else {
this->b = new int[ob.n];
for (int i = 0; i < ob.n; i++)
this->b[i] = ob.b[i];
}
}
BigInteger::BigInteger(const int c) {
if (c <= 0) {
this->n = 1;
this->b = new int[1];
this->b[0] = 0;
} else {
int *newbody;
int bodysize = 0;
int i, j, r, cc, pos;
this->b = 0;
this->n = 0;
cc = c;
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 int[this->n + 1];
for (j = 0; j < this->n; j++)
newbody[j] = this->b[j];
newbody[j] = r; /* j == this->n */
delete this->b;
this->b = newbody;
this->n++;
}
}
assert(this->n != 0);
}
BigInteger &BigInteger::operator=(BigInteger ob) {
this->n = ob.n;
if (ob.n == 0) {
delete [] this->b;
this->b = 0;
} else {
delete [] this->b;
this->b = new int[ob.n];
for (int i = 0; i < ob.n; i++) {
this->b[i] = ob.b[i];
}
}
return *this;
}
BigInteger::~BigInteger() {
delete [] this->b;
this->b = 0;
this->n = 0;
}
bool operator==(BigInteger const &a, BigInteger const &b) {
int i, more, 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;
}
}
if (a.n < b.n) {
for (; i < b.n; i++)
if (b.b[i] != 0) {
isEqual = false;
}
} else {
for (;i < a.n; i++)
if (a.b[i] != 0) {
isEqual = false;
}
}
return isEqual;
}
bool operator!=(BigInteger const &a, BigInteger const &b) { return !(a == b); }
BigInteger operator+(BigInteger const &a, BigInteger const &b) {
BigInteger r;
BigInteger const * more_ab;
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 int [r.n];
int i, carry = 0;
for (i = 0; i < less_n; i++) {
int 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++) {
int 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 */ /* not to insert break keyword.*/
}
}
if (carry) {
int *new_body = new int [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; /* need */
r.n++;
}
return r;
}
BigInteger operator-(BigInteger const &a, BigInteger const &b) {
int dmy;
return sub(a, b, dmy);
}
bool operator<(BigInteger const &a, BigInteger const &b) {
int borrow;
sub(a, b, borrow);
if (borrow != 0) {
return true;
} else {
return false;
}
}
bool operator<=(BigInteger const &a, BigInteger const &b) {
if (a < b)
return true;
if (a == b)
return true;
return false;
}
BigInteger sub(BigInteger const &a, BigInteger const &b, int &borrowR) {
int vCount, moreCount, i;
int diff;
bool flagMore, flagLess;
BigInteger 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;
}
}
}
// std::cout << a << "-" << b << "==" << r << ":" << borrowR << " ";
// std::cout << "a.n=" << a.n <<",b.n=" << b.n << std::endl;
return r;
}
BigInteger operator*(BigInteger const &a, BigInteger const &b) {
return mul2(a, b);
}
BigInteger mul2(BigInteger const &a, BigInteger const &b) {
BigInteger Rshift = b;
BigInteger Lshift = a;
BigInteger r = 0;
int lsb;
while (!BigInteger::iszero(Rshift)) {
BigInteger::RightShift(Rshift, lsb);
if (lsb) {
r = r + Lshift;
}
BigInteger::LeftShift(Lshift);
}
return r;
}
void BigInteger::LeftShift(BigInteger &a) {
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) {
int *newbody;
newbody = new int [a.n + 1];
newbody[a.n] = 1;
for (int i = 0; i < a.n; i++) {
newbody[i] = a.b[i];
}
a.n++;
delete a.b;
a.b = newbody;
}
}
void BigInteger::RightShift(BigInteger &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) {
int *newbody;
newbody = new int [a.n - 1];
for (int i = 0; i < a.n - 1; i++)
newbody[i] = a.b[i];
a.n--;
delete a.b;
a.b = newbody;
}
}
BigInteger mul1(BigInteger const &a, BigInteger const &b) {
BigInteger r = 0;
for (BigInteger i = BigInteger(0); i < b; i = i + 1)
r = r + a;
return r;
}
void BigInteger::LeftShift2(int &msb, BigInteger &a) {
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 BigInteger::LeftShift3(BigInteger &a, int msb) {
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) {
int *newbody;
newbody = new int [a.n + 1];
newbody[a.n] = 1;
for (int i = 0; i < a.n; i++) {
newbody[i] = a.b[i];
}
a.n++;
delete a.b;
a.b = newbody;
}
}
void div2(BigInteger const &a, BigInteger const &b, BigInteger &q, BigInteger &r) {
if (b == BigInteger(0)) {
std::cout << "null devided." << std::endl;
return;
}
/* LeftRest <- LeftShiftBuff */
BigInteger LeftRest(0);
BigInteger LeftShiftBuff = a;
BigInteger 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;
BigInteger::LeftShift2(msb, LeftShiftBuff);
BigInteger::LeftShift3(LeftRest, msb);
lsb = 0;
if (b <= LeftRest) {
LeftRest = LeftRest - b;
lsb = 1;
}
BigInteger::LeftShift3(Quotient, lsb);
// std::cout << "Quotient=" << Quotient << std::endl;
n--;
}
q = Quotient;
r = LeftRest;
}
BigInteger operator/(BigInteger const &a, BigInteger const &b) {
BigInteger q, r;
div2(a, b, q, r);
return q;
}
BigInteger operator%(BigInteger const &a, BigInteger const &b){
BigInteger q, r;
div2(a, b, q, r);
return r;
}
BigInteger div1(BigInteger const &a, BigInteger const &b, BigInteger &r) {
BigInteger q(0);
BigInteger rest = a;
while ((b < rest) || (b == rest)) {
q = q + BigInteger(1);
rest = rest - b;
}
r = rest;
return q;
}
bool BigInteger::iszero(BigInteger &n) {
bool isZero = true;
for (int i = 0; i < n.n; i++)
if (n.b[i] != 0) {
isZero = false;
break;
}
return isZero;
}
std::ostream &operator<<(std::ostream &stream, BigInteger c) {
std::basic_string<char> mod10;
BigInteger q, n;
int mod;
bool fzero;
fzero = true;
n = c;
for(;;) {
/* div10(n, q, mod); */
{
q = n;
mod = 0;
for (int i = 0; i < n.n * BIT; i++) {
/* shift_div(mod, q); */
{
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 (BigInteger::iszero(q) && mod == 0)
break;
mod10 = (char)('0' + mod) + mod10;
fzero = false;
n = q;
}
if (fzero)
stream << '0';
else
stream << mod10;
return stream;
}
int main() {
BigInteger s;
for (int n = 1; n <= 100; n++) {
BigInteger t(n);
s = s + t;
}
std::cout << s << std::endl;
const int a = 1234;
const int b = 123;
// r = 12345C1234
BigInteger r(1);
int l, m, n;
for (l = 1, m = a, n = b; n > 0; m--, n--, l++) {
BigInteger s1(m);
BigInteger s2(l);
r = r * s1;
r = r / s2;
}
std::cout << r << std::endl;
return 0;
}
/* end */