#include <iostream>
#include <string>
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
class bigint
{
private:
char sign; //+:0, -:1
unsigned *dats; //가장 뒷자리가 dats[0]에 저장
unsigned len; //dats배열 길이
public:
unsigned cona2u(char*);
bigint();
~bigint();
bigint(const int);
bigint(const char*);
bigint(const bigint &);
unsigned resize(unsigned); //길이조절
unsigned resize(); //앞의 0 지우기
bigint abs(); //절대값
bigint negative(unsigned); //1의보수
int cmp(bigint &b); //strcmp와 리턴값 같음
bigint _or(bigint &b); //this에 저장
bigint _and(bigint &b); //this에 저장
bigint _xor(bigint &b); //this에 저장
bigint shr(unsigned n); //this에 (this>>n)을 저장
bigint shl(unsigned n); //this에 (this<<n)을 저장
bigint add(bigint &b); //this에 (this+b)를 저장, 리턴
bigint sub(bigint &b); //this에 (this-b)를 저장, 리턴
bigint mul(bigint &b); //(this*b)를 리턴
bigint mul_lr(bigint &b); //(this*b)를 리턴, A la russe알고리즘, 느려
bigint div(bigint &b, int); //(this/b)또는 (this%b)리턴
char* con10(); //10진수 출력
bigint operator=(const int);
bigint operator=(const bigint &);
bigint operator=(const char*);
friend bigint operator|(bigint, bigint);
friend bigint operator&(bigint, bigint);
friend bigint operator^(bigint, bigint);
friend bigint operator+(bigint, bigint);
friend bigint operator-(bigint, bigint);
friend bigint operator*(bigint, bigint);
friend bigint operator/(bigint, bigint);
friend bigint operator%(bigint, bigint);
friend bool operator<(bigint, bigint);
friend bool operator<=(bigint, bigint);
friend bool operator>(bigint, bigint);
friend bool operator>=(bigint, bigint);
friend bool operator==(bigint, bigint);
friend bool operator!=(bigint, bigint);
bigint operator|=(bigint);
bigint operator&=(bigint);
bigint operator^=(bigint);
bigint operator+=(bigint);
bigint operator-=(bigint);
bigint operator*=(bigint);
bigint operator/=(bigint);
bigint operator%=(bigint);
friend std::ostream& operator <<( std::ostream& os, bigint b );
friend std::istream& operator >>( std::istream& is, bigint& b );
};
unsigned bigint::cona2u(char *src)
{
unsigned ten, sum, eos=strlen(src)-1;
for(sum=0, ten=1; (int)eos>=0 && ten<=100000000; ten*=10, eos--)
{
sum+=ten*(src[eos]-'0');
src[eos]=0;
}
return sum;
}
bigint::bigint()
{
len=1;
sign=0;
dats=(unsigned*)calloc(1,sizeof(unsigned));
}
bigint::~bigint()
{
free(dats);
}
bigint::bigint(const int src)
{
len=1;
sign=0;
dats=(unsigned*)malloc(sizeof(unsigned)*len);
dats[0]=src;
}
bigint::bigint(const char *src)
{
char *str=(char*)malloc(sizeof(char)*(strlen(src)+1));
sign=0;
strcpy(str, src);
if(src[0]=='-')
strcpy(str,src+1), sign=1;
if(src[0]=='+')
strcpy(str,src+1);
len=(strlen(src)-1)/9 + 1;
dats=(unsigned*)malloc(sizeof(unsigned)*len);
unsigned i;
for(i=0; i<len; i++)
{
dats[i]=cona2u(str);
}
free(str);
shl(len*32); //
unsigned j, lmt=len/2;
for(i=(len/2)*32; i; i--)
{
shr(1);
for(j=len-1; j>=lmt; j--)
{
if(dats[j]>=2147483648)
dats[j]-=1647483648;
}
}
}
bigint::bigint(const bigint &src)
{
len=src.len;
sign=src.sign;
dats=(unsigned*)malloc(sizeof(unsigned)*len);
memcpy(dats, src.dats, sizeof(unsigned)*len);
}
unsigned bigint::resize(unsigned len_new)
{
if(len==len_new)
return len;
unsigned *new_p=(unsigned*)malloc(sizeof(unsigned)*len_new); //
memcpy(new_p, dats, sizeof(unsigned)*((len<len_new)?len:len_new)); //이부분에 realloc(dats, sizeof(unsigned)*len_new)쓰면 왜 값이 바뀌나요
free(dats); //
dats=new_p; //
if(len < len_new)
memset(dats+len, 0, sizeof(unsigned)*(len_new-len));
len=len_new;
return len;
}
unsigned bigint::resize()
{
unsigned i;
for(i=len-1; dats[i]==0; i--);
i++;
if(i)
resize(i);
else
resize(1);
return len;
}
bigint bigint::abs()
{
bigint toreturn(*this);
toreturn.sign=0;
return toreturn;
}
//1의 보수
bigint bigint::negative(unsigned len_new)
{
bigint toreturn(*this);
toreturn.resize(len_new);
for(unsigned i=0; i<len_new; i++)
toreturn.dats[i]=~toreturn.dats[i];
return toreturn;
}
int bigint::cmp(bigint &b)
{
if(sign==1 && b.sign==0)
return -1;
if(sign==0 && b.sign==1)
return 1;
int left=1, right=-1;
if(sign==1 && b.sign==1)
left=-1, right=1;
if(len>b.len)
return left;
if(len<b.len)
return right;
for(int i=len-1; i>=0; i--)
{
if(dats[i]>b.dats[i])
return left;
if(dats[i]<b.dats[i])
return right;
}
return 0;
}
bigint bigint::_or(bigint &b)
{
if(len<b.len)
resize(b.len);
unsigned i;
for(i=0; i<len; i++)
dats[i]|=b.dats[i];
return *this;
}
bigint bigint::_and(bigint &b)
{
if(len<b.len)
resize(b.len);
unsigned i;
for(i=0; i<len; i++)
dats[i]&=b.dats[i];
return *this;
}
bigint bigint::_xor(bigint &b)
{
if(len<b.len)
resize(b.len);
unsigned i;
for(i=0; i<len; i++)
dats[i]^=b.dats[i];
return *this;
}
bigint bigint::shr(unsigned n)
{
unsigned move=n>>5, cut=n&31, i, j, tmp;
dats[0]=dats[move]>>cut;
for(i=1; i<len-move; i++)
{
for(j=0, tmp=dats[i+move]; j<32-cut; j++) //dats[i+1]=dats[i+1]|(dats[i+move]<<(32-cut));
tmp<<=1; //
dats[i-1]|=tmp;
dats[i]=dats[i+move]>>cut;
}
resize(len-move);//옮겨진 부분 삭제
resize();
return *this;
}
bigint bigint::shl(unsigned n)
{
unsigned move=n>>5, cut=n&31, i, j, tmp;
resize(len+move+1);
dats[len-1]=dats[len-move-1]<<cut;
for(i=len-2; (int)i>=(int)move; i--)
{
for(j=0, tmp=dats[i-move]; j<32-cut; j++) //dats[i+1]=dats[i+1]|(dats[i-move]>>(32-cut));
tmp>>=1; //
dats[i+1]=dats[i+1]|tmp;
dats[i]=dats[i-move]<<cut;
}
memset(dats, 0, sizeof(unsigned)*move);//뒤에 옮겨진 부분 0으로
resize();
return *this;
}
bigint bigint::add(bigint &b)
{
long long carry=0;
unsigned i;
resize( ((b.len>len)?b.len:len) + 1 );
for(i=0; i<b.len; i++)
{
carry = (long long)dats[i] + (long long)b.dats[i] + carry;
dats[i]=carry&(((long long)1<<32)-1);
carry>>=32;
}
for(; carry; i++)
{
carry=(long long)dats[i] + carry;
dats[i]=carry&(((long long)1<<32)-1);
carry>>=32;
}
resize();
return *this;
}
//1의 보수 사용
bigint bigint::sub(bigint &b)
{
bigint subtrahend(b); //감수
//resize(len);
unsigned len_new=((len>b.len)?len:b.len);
subtrahend=subtrahend.negative(len_new);
add(subtrahend);
if(len > len_new)//자리올림수있으면
{
resize(len_new);
add((bigint)1);
}
else//자리올림수 없으면
{
*this=negative(len_new);
sign=1;
}
return *this;
}
bigint bigint::mul(bigint &b)
{
bigint result, tmp;
unsigned i, j;
long long carry;
for(i=0; i<b.len; i++)
{
tmp.resize(len+1+i);
for(carry=j=0; j<len; j++)
{
carry=(long long)dats[j]*(long long)b.dats[i]+carry;
tmp.dats[j+i]=(unsigned)carry&(((long long)1<<32)-1);
carry>>=32;
}
tmp.dats[j+i]=(unsigned)carry;
result.add(tmp);
memset(tmp.dats, 0, sizeof(unsigned)*tmp.len);
}
result.resize();
return result;
}
bigint bigint::mul_lr(bigint &b)
{
bigint sum(0), tmp(b);
while( cmp((bigint)0) != 0)
{
if(dats[0]&1)
sum.add(tmp);
shr(1);
tmp.shl(1);
}
return sum;
}
bigint bigint::div(bigint &b, int ask_mod=0)
{
bigint r=*this, q=0, tmp=b, one=1;
unsigned i;
for(i=0;tmp.cmp(r)<=0;tmp.shl(1),i++);
i--;
tmp.shr(1);
one.shl(i);
while(b.cmp(r)<=0)//b<=r
{
for(;tmp.cmp(r)>0;tmp.shr(1),one.shr(1));
q._or( one );
r.sub(tmp);
}
*this=q;
if(ask_mod)
return r;
return *this;
}
char* bigint::con10()
{
bigint tmp(*this);
unsigned i, j, lmt=tmp.len;
char *str, str_tmp[10];
for(i=tmp.len*32; i; i--)
{
for(j=tmp.len-1; j>=lmt; j--)
{
if(tmp.dats[j] >= 500000000)
tmp.dats[j]+=1647483648;
}
tmp.shl(1);
}
i=tmp.len-1;
str=(char *)calloc((tmp.len-lmt)*9, sizeof(char));
sprintf(str_tmp,"%u", tmp.dats[i]);
strcat(str, str_tmp);
if(i)
{
for(--i; i>=lmt; i--)
{
sprintf(str_tmp,"%09u",tmp.dats[i]);
strcat(str, str_tmp);
}
}
return str;
}
bigint bigint::operator=(const int src)
{
resize(1);
sign=0;
dats[0]=src;
if(src<0)
sign=1, dats[0]*=-1;
return *this;
}
bigint bigint::operator=(const bigint &src)
{
resize(src.len);
sign=src.sign;
memcpy(dats, src.dats, sizeof(unsigned)*len);
return *this;
}
bigint bigint::operator=(const char *src)
{
char *str=(char*)malloc(sizeof(char)*(strlen(src)+1));
sign=0;
strcpy(str, src);
if(src[0]=='-')
strcpy(str,src+1), sign=1;
if(src[0]=='+')
strcpy(str,src+1);
resize((strlen(src)-1)/9 + 1);
unsigned i;
for(i=0; i<len; i++)
{
dats[i]=cona2u(str);
}
free(str);
shl(len*32);
unsigned j, lmt=len/2;
for(i=(len/2)*32; i; i--)
{
shr(1);
for(j=len-1; j>=lmt; j--)
{
if(dats[j]>=2147483648)
dats[j]-=1647483648;
}
}
return *this;
}
bigint operator|(bigint a, bigint b)
{
return a._or(b);
}
bigint operator&(bigint a, bigint b)
{
return a._and(b);
}
bigint operator^(bigint a, bigint b)
{
return a._xor(b);
}
bigint operator+(bigint a, bigint b)
{
if(a.sign==b.sign)
return a.add(b);
if(a.sign==0 && b.sign==1)
return a.sub(b);
//a.sign==1 && b.sign==0
return b.sub(a);
}
bigint operator-(bigint a, bigint b)
{
if(a.sign==1 && b.sign==1)
{
b.sign=0;
if((a.abs()).cmp(b.abs())==1)
b.sign=1;
b.sub(a);
return b;
}
if(a.sign==0 && b.sign==0)
return a.sub(b);
if(a.sign==0 && b.sign==1)
return a.add(b);
//a.sign==1 && b.sign==0
a.add(b);
a.sign=1;
return a;
}
bigint operator*(bigint a, bigint b)
{
bigint toreturn=a.mul(b);
toreturn.sign=a.sign^b.sign;
return toreturn;
}
bigint operator/(bigint a, bigint b)
{
bigint toreturn=a.div(b);
toreturn.sign=a.sign^b.sign;
return toreturn;
}
bigint operator%(bigint a, bigint b)
{
bigint toreturn=a.div(b,1);
toreturn.sign=a.sign;
return toreturn;
}
bool operator<(bigint a, bigint b)
{
if(a.cmp(b)<0)
return true;
return false;
}
bool operator<=(bigint a, bigint b)
{
if(a.cmp(b)<=0)
return true;
return false;
}
bool operator>(bigint a, bigint b)
{
if(a.cmp(b)>0)
return true;
return false;
}
bool operator>=(bigint a, bigint b)
{
if(a.cmp(b)>=0)
return true;
return false;
}
bool operator==(bigint a, bigint b)
{
if(a.cmp(b)==0)
return true;
return false;
}
bool operator!=(bigint a, bigint b)
{
if(a.cmp(b)==0)
return false;
return true;
}
bigint bigint::operator|=(bigint b)
{
if(len!=b.len)
{
resize((len>b.len)?len:b.len);
b.resize((len>b.len)?len:b.len);
}
_or(b);
resize();
return *this;
}
bigint bigint::operator&=(bigint b)
{
if(len!=b.len)
{
resize((len>b.len)?len:b.len);
b.resize((len>b.len)?len:b.len);
}
_and(b);
resize();
return *this;
}
bigint bigint::operator^=(bigint b)
{
if(len!=b.len)
{
resize((len>b.len)?len:b.len);
b.resize((len>b.len)?len:b.len);
}
_xor(b);
resize();
return *this;
}
bigint bigint::operator+=(bigint b)
{
if(sign==b.sign)
return add(b);
if(sign==0 && b.sign==1)
return sub(b);
//a.sign==1 && b.sign==0
return *this=b.sub(*this);
}
bigint bigint::operator-=(bigint b)
{
if(sign==1 && b.sign==1)
{
b.sign=0;
if((abs()).cmp(b.abs())==1)
b.sign=1;
return *this=b.sub(*this);
}
if(sign==0 && b.sign==0)
return sub(b);
if(sign==0 && b.sign==1)
return add(b);
//a.sign==1 && b.sign==0
sign=1;
return add(b);
}
bigint bigint::operator*=(bigint b)
{
*this=mul(b);
sign=sign^b.sign;
return *this;
}
bigint bigint::operator/=(bigint b)
{
*this=div(b);
sign=sign^b.sign;
return *this;
}
bigint bigint::operator%=(bigint b)
{
*this=div(b,1);
return *this;
}
std::ostream& operator <<(std::ostream& os, bigint b )
{
char *tmp=b.con10();
os << ((b.sign == 1)? "-": "") << tmp;
free(tmp);
return os;
}
std::istream& operator >>(std::istream& is, bigint& b )
{
std::string numstr;
is >> numstr;
b = numstr.c_str();
return is;
}
int main()
{
return 0;
}