chyx's Blog

一个简单的大整数模板，使用了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();
}