~cpp
//////////////////////////////////////////////////////////////////////////
// Big Integer Class - C++
// 만든이 : Moon, Bo-chang.
// 만든 날짜 : 2006 / 1 / 7
// 마지막으로 수정한 날짜 :
// 주의 : 오버플로우 처리 안함
// 지원하는 연산 : +(덧셈), -(뺄셈), *(곱셈), /(나눗셈) - 나눗셈 연산에서 나머지는 버린다.
// 함수 호출이 모두 복사로 이루어지므로 성능이 크게 떨어진다.
//////////////////////////////////////////////////////////////////////////
#pragma once
#include <iostream>
using namespace std;
#include <cstring>
#define MAXDIGITS 100
#define PLUS 1
#define MINUS -1
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
class BigInteger
{
public:
char digit[MAXDIGITS];
int signbit;
int lastdigit;
public:
BigInteger(int n)
{
int i;
lastdigit = 0;
signbit = (n < 0) ? MINUS : PLUS;
while (n / 10)
{
digit[lastdigit++] = n % 10;
n /= 10;
}
digit[lastdigit] = n % 10;
for (i = lastdigit + 1; i < MAXDIGITS; i++)
digit[i] = 0;
}
BigInteger()
{
int i;
for (i = 0; i < MAXDIGITS; i++)
digit[i] = 0;
signbit = PLUS;
lastdigit = 0;
}
void print()
{
if (signbit == MINUS) cout << "-";
for (int i = lastdigit; i >= 0; i--)
cout << (int)digit[i];
}
void input()
{
int startI = 0;
int i, j;
char temp[MAXDIGITS];
while (cin.peek() == ' ' || cin.peek() == '\n')
cin.get();
cin >> temp;
lastdigit = strlen(temp) - 1;
signbit = PLUS;
if (temp[0] == '-')
{
signbit = MINUS;
startI = 1;
lastdigit--;
}
else if (temp[0] == '+')
{
startI = 1;
lastdigit--;
}
j = 0;
for (i = lastdigit + startI; i >= startI; i--)
digit[j++] = temp[i] - '0';
}
public:
friend void elminatePreZero(BigInteger& n)
{
while (n.lastdigit > 0 && n.digit[n.lastdigit] == 0)
n.lastdigit--;
if (n.lastdigit == 0 && n.digit[0] == 0)
n.signbit = PLUS;
}
friend int compare(BigInteger& a, BigInteger& b)
{
int i;
if (a.signbit == MINUS && b.signbit == PLUS) return PLUS;
if (a.signbit == PLUS && b.signbit == MINUS) return MINUS;
if (b.lastdigit > a.lastdigit) return (PLUS * a.signbit);
if (a.lastdigit > b.lastdigit) return (MINUS * a.signbit);
for (i = a.lastdigit; i >= 0; i--)
{
if (a.digit[i] > b.digit[i])
return (MINUS * a.signbit);
if (b.digit[i] > a.digit[i])
return (PLUS * a.signbit);
}
return 0;
}
friend void shiftDigit(BigInteger& n, int d)
{
int i;
if (n.lastdigit == 0 && n.digit[0] == 0) return;
for (i = n.lastdigit; i >= 0; i--)
n.digit[i+d] = n.digit[i];
for (i = 0; i < d; i++) n.digit[i] = 0;
n.lastdigit = n.lastdigit + d;
}
friend BigInteger operator+(BigInteger a, BigInteger b)
{
int carry;
BigInteger ret;
int i;
if (a.signbit == MINUS && b.signbit == PLUS)
{
a.signbit = PLUS;
ret = b - a;
a.signbit = MINUS;
}
else if (a.signbit == PLUS && b.signbit == MINUS)
{
b.signbit = PLUS;
ret = a - b;
b.signbit = MINUS;
}
else
{
ret.signbit = a.signbit;
ret.lastdigit = MAX(a.lastdigit, b.lastdigit) + 1;
carry = 0;
for (i = 0; i <= ret.lastdigit; i++)
{
ret.digit[i] = (carry + a.digit[i] + b.digit[i]) % 10;
carry = (carry + a.digit[i] + b.digit[i]) / 10;
}
elminatePreZero(ret);
}
return ret;
}
friend BigInteger operator-(BigInteger a, BigInteger b)
{
BigInteger ret;
int borrow, v;
int i;
if (a.signbit == MINUS || b.signbit == MINUS)
{
b.signbit = -1 * b.signbit;
ret = a + b;
b.signbit = -1 * b.signbit;
return ret;
}
if (compare(a,b) == PLUS)
{
ret = b - a;
ret.signbit = MINUS;
return ret;
}
ret.lastdigit = MAX(a.lastdigit,b.lastdigit);
borrow = 0;
for (i = 0; i <= ret.lastdigit; i++)
{
v = a.digit[i] - borrow - b.digit[i];
if (a.digit[i] > 0)
borrow = 0;
if (v < 0)
{
v = v + 10;
borrow = 1;
}
ret.digit[i] = v % 10;
}
elminatePreZero(ret);
return ret;
}
friend BigInteger operator*(BigInteger a, BigInteger b)
{
BigInteger row, tmp, ret;
int i, j;
row = a;
for (i = 0; i <= b.lastdigit; i++)
{
for (j = 1; j <= b.digit[i]; j++)
{
tmp = ret + row;
ret = tmp;
}
shiftDigit(row, 1);
}
ret.signbit = a.signbit * b.signbit;
elminatePreZero(ret);
return ret;
}
friend BigInteger operator/(BigInteger a, BigInteger b)
{
BigInteger row, tmp, ret;
int asign, bsign;
int i;
ret.signbit = a.signbit * b.signbit;
asign = a.signbit;
bsign = b.signbit;
a.signbit = PLUS;
b.signbit = PLUS;
ret.lastdigit = a.lastdigit;
for (i = a.lastdigit; i >= 0; i--)
{
shiftDigit(row, 1);
row.digit[0] = a.digit[i];
ret.digit[i] = 0;
while (compare(row, b) != PLUS)
{
ret.digit[i]++;
tmp = row - b;
row = tmp;
}
}
elminatePreZero(ret);
a.signbit = asign;
b.signbit = bsign;
return ret;
}
};