1
23
2010
0

大整数模板

一个简单的大整数模板,使用了vector来实现,效率应该会灰常低,不过估计打起来会比较快吧,至少在Topcoder上是有用的


#define ll long long
#define SZ size()

ll BASE = 1000000000;
struct BigInteger{
vector<ll> num;
void operator+=(const BigInteger& other){
vector<ll>& a = num;
const vector<ll>& b = other.num; // const CE!
a.resize( max(a.size(), b.size()) + 1, 0);
Rep(i,b.size()) if( (a[i] += b[i]) >= BASE ) a[i] -= BASE, a[i+1]++;
for( int i = b.size(); a[i] >= BASE ; ++i) a[i] -= BASE, a[i+1]++;
if( a.SZ >= 2 && a.back() == 0 ) a.resize( a.size() - 1);
}

void operator-=(const BigInteger& other){
                // 默认this >=
vector<ll>& a = num;
const vector<ll>& b = other.num; // const CE!
a.resize( max(a.size(), b.size()) + 1, 0);
Rep(i,b.size()) if( (a[i] -= b[i]) < 0 ) a[i] += BASE, a[i+1]--;
for( int i = b.size(); a[i] < 0; ++i) a[i] += BASE, a[i+1]--;
if( a.SZ >= 2 && !a.back()) a.resize( a.size() - 1);
}

void print(){
printf("%lld", num.back());
                                                // remember to change length
for(int i = num.size() - 2; i>= 0; --i)printf("%09lld", num[i]);        
        }         void scan(){
char str[1000];
scanf("%s", str);
int n = strlen(str);
num.resize((n+3)/4, 0); // ceil
for(int i = 0; i < n; ++i) num[(n-1-i)/4] = num[(n-1-i)/4]*10 + str[i] - '0';
}
void init(int a){
num.clear();
if( a < 0 ) a = 0;
for(; a; a/=BASE) num.push_back( a % BASE );
if( num.size() == 0 ) num.push_back(0);
}                 // return the remainder, b is int int operator/=(int b){
int c = 0;
for(int i = num.size() - 1; i>=0; --i){
c = c * BASE + num[i];
num[i] = c / b;
c %= b;
}
while( num.size() >= 2 && num.back() == 0 ) num.resize( num.size() - 1 );
return c;
}
BigInteger(int a = 0){
init(a);
}
};
BigInteger operator*(const BigInteger& _a, const BigInteger& _b){
BigInteger _c;
const vector<ll>& a = _a.num; // const CE!
const vector<ll>& b = _b.num; // const CE!
vector<ll>& c = _c.num;
c = vector<ll>(a.size() + b.size(), 0);
Rep(i,a.size())Rep(j,b.size()){
if( (c[i+j] += a[i] * b[j]) >= BASE )c[i+j+1] += c[i+j] / BASE, c[i+j] %= BASE;
}
while( c.SZ >= 2 && !c.back() )c.resize( c.size() - 1); Rep(i,c.SZ)assert(0<=c[i] && c[i] < BASE ); // 对调试很有帮助的断言
return _c;
}
bool operator==(const BigInteger& a, const BigInteger& b){return a.num == b.num;}
bool operator < (const BigInteger& a, const BigInteger& b ){
if( a.num.size() == b.num.size() )                return lexicographical_compare(a.num.rbegin(), a.num.rend(), b.num.rbegin(), b.num.rend()) ;
return a.num.size() < b.num.size();
}

 

 

Category: 未分类 | Tags: | Read Count: 1067

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com