C++大整数テンプレート
4618 ワード
#define MAXN 9999
#define DLEN 4
class Bignum
{
private:
int a[10010],len;
public:
Bignum(){ len=1; memset( a , 0 , sizeof(a) ); }
Bignum( const int );
Bignum( const char* );
Bignum &operator=( const Bignum & );
Bignum operator+( const Bignum & )const;
Bignum operator-( const Bignum & )const;
Bignum operator*( const Bignum & )const;
Bignum operator/( const int & )const;
Bignum operator^( const int & )const;
int operator%( const int & )const;
bool operator>( const Bignum&T )const;
bool operator>( const int &t )const;
void print();
};
Bignum::Bignum( const int b )
{
int c,d=b;
len = 0;
memset ( a , 0 , sizeof(a) );
while ( d>MAXN )
{
c = d-(d/(MAXN+1))*(MAXN+1);
d = d/(MAXN+1);
a[len++] = c;
}
a[len++] = d;
}
Bignum::Bignum( const char*s )
{
memset ( a , 0 , sizeof(a) );
int L = strlen(s);
len = L/DLEN;
if ( L%DLEN ) len++;
int index = 0;
for( int i=L-1 ; i>=0 ; i-=DLEN )
{
int t = 0;
int k = i-DLEN+1;
if ( k<0 ) k = 0;
for ( int j=k ; j<=i ; j++ )
t = t*10+s[j]-'0';
a[index++] = t;
}
}
Bignum & Bignum::operator=( const Bignum &n )
{
len = n.len;
memset ( a , 0 , sizeof(a) );
for ( int i=0 ; ilen?T.len:len;
for ( int i=0 ; iMAXN )
{
t.a[i+1]++;
t.a[i] -= MAXN+1;
}
}
if ( t.a[big]!=0 )
t.len = big+1;
else
t.len = big;
return t;
}
Bignum Bignum::operator-( const Bignum &T )const
{
bool flag;
Bignum t1,t2;
if ( *this>T )
{
t1 = *this;
t2 = T;
flag = 0;
}
else
{
t1 = T;
t2 = *this;
flag = 1;
}
int big = t1.len;
for ( int i=0 ; ii )
t1.a[j--] += MAXN;
t1.a[i] += MAXN+1-t2.a[i];
}
else
t1.a[i] -= t2.a[i];
}
t1.len = big;
while ( t1.a[t1.len-1]==0&&t1.len>1 )
t1.len--;
if ( flag )
t1.a[t1.len-1] = 0-t1.a[t1.len-1];
return t1;
}
Bignum Bignum::operator*( const Bignum&T )const
{
Bignum ret;
int i,j,up;
int temp,temp1;
for ( i=0 ; iMAXN )
{
temp1 = temp-temp/(MAXN+1)*(MAXN+1);
up = temp/(MAXN+1);
ret.a[i+j] = temp1;
}
else
{
up = 0;
ret.a[i+j] = temp;
}
}
if ( up!=0 )
ret.a[i+j] = up;
}
ret.len = i+j;
while ( ret.a[ret.len-1]==0&&ret.len>1 ) ret.len--;
return ret;
}
Bignum Bignum::operator/( const int &b )const
{
Bignum ret;
int down=0;
for ( int i=len-1 ; i>=0 ; i-- )
{
ret.a[i] = (a[i]+down*(MAXN+1))/b;
down = a[i]+down*(MAXN+1)-ret.a[i]*b;
}
ret.len = len;
while ( ret.a[ret.len-1]==0&&ret.len>1 )
ret.len--;
return ret;
}
int Bignum::operator%( const int &b )const
{
int d = 0;
for ( int i=len-1 ; i>=0 ; i-- )
d = ( (1LL*d*(MAXN+1))%b+a[i] )%b;
return d;
}
Bignum Bignum::operator^( const int &n )const
{
Bignum t,ret(1);
if ( n<0 ) exit(-1);
if ( n==0 ) return 1;
if ( n==1 ) return *this;
int m = n,i;
while ( m>1 )
{
t = *this;
for ( i=1 ; (i<<1)<=m ; i<<=1 )
t = t*t;
m -= i;
ret = ret*t;
if ( m==1 )
ret = ret*(*this);
}
return ret;
}
bool Bignum::operator>( const Bignum &T )const
{
int ln;
if ( len>T.len ) return true;
else if ( len==T.len )
{
ln = len-1;
while ( a[ln]==T.a[ln]&&ln>=0 )
ln--;
if ( ln>=0&&a[ln]>T.a[ln] )
return true;
else
return false;
}
else
return false;
}
bool Bignum::operator>( const int &t )const
{
Bignum b(t);
return *this>b;
}
void Bignum::print()
{
int i;
printf( "%d" , a[len-1] );
for ( int i=len-2 ; i>=0 ; i-- )
printf( "%04d" , a[i] );
printf( "
" );
}