1368.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1368 on 2006-01-20 at 13:38:37 */ 
#include <cstdio>
#include <cstring>

const int MAX = 160;
const int MAXLEN = 4;
const int L_MAX = MAXLEN * MAX;
const int f[10] = { 1, 10, 100, 1000, 10000 };

class HugeInt {
private:
	int n[MAX], length;
	int getlen(int) const;
	void operator <<=(const int);
	void div10();
	int times(const HugeInt&);
public:
	HugeInt();
	void make(char*);
	int compareTo(const HugeInt&) const;
	void operator +=(const HugeInt&);
	void operator -=(const HugeInt&);
	void operator *=(const HugeInt&);
	void divide(const HugeInt&, int);
	void print(char) const;
};
int HugeInt::getlen(int m) const {
	int l;
	for(l = 0; m != 0; l++) m /= 10;
	return l;
}
void HugeInt::operator <<=(const int m) {
	int i, x = m / MAXLEN, r = m % MAXLEN;
	length += m;
	for(i = MAX-1-x; i >= 0; i--) {
		n[i+x] = n[i] * f[r];
		if(n[i+x] >= f[MAXLEN]) {
			n[i+x+1] += n[i+x] / f[MAXLEN];
			n[i+x] %= f[MAXLEN];
		}
		if(x > 0) n[i] = 0;
	}
}
void HugeInt::div10() {
	int i, m = 0;
	for(i = MAX-1; i >= 0; i--) {
		n[i] += m * f[MAXLEN];
		m = n[i] % 10;
		n[i] /= 10;
	}
}
int HugeInt::times(const HugeInt& hi) {
	int l;
	for(l = 0; compareTo(hi) >= 0; l++) *this -= hi;
	return l;
}
HugeInt::HugeInt() {
	memset(n, 0, sizeof(n));
}
void HugeInt::make(char *line) {
	length = strlen(line);
	int r = length % MAXLEN, q = length / MAXLEN;
	int i, j;
	memset(n, 0, sizeof(n));
	for(i = 0; i < r; i++)
		n[q] = n[q] * 10 + line[i] - '0';
	for(i = q-1; i >= 0; i--)
		for(j = 0; j < MAXLEN; j++)
			n[i] = n[i] * 10 + line[(q-1-i)*MAXLEN+j+r] - '0';
}
int HugeInt::compareTo(const HugeInt& hi) const {
	int i;
	for(i = MAX-1; i >= 0; i--)
		if(n[i] < hi.n[i]) return -1;
		else if(n[i] > hi.n[i]) return 1;
	return 0;
}
void HugeInt::operator +=(const HugeInt& hi) {
	int i, j;
	for(i = 0; i < MAX; i++) {
		n[i] += hi.n[i];
		for(j = 0; n[i+j] >= f[MAXLEN]; j++) {
			n[i+j+1] += n[i+j] / f[MAXLEN];
			n[i+j] %= f[MAXLEN];
		}
	}
}
void HugeInt::operator -=(const HugeInt& hi) {
	int i;
	for(i = 0; i < MAX; i++) {
		n[i] -= hi.n[i];
		while(n[i] < 0)
			n[i] += f[MAXLEN], n[i+1]--;
	}
}
void HugeInt::operator *=(const HugeInt& hi) {
	int i, j, k;
	HugeInt b;
	int p = (hi.length + MAXLEN - 1) / MAXLEN;
	int q = (length + MAXLEN - 1) / MAXLEN;
	for(i = 0; i < p; i++)
		for(j = 0; j < q; j++) {
			b.n[i+j] += hi.n[i] * n[j];
			for(k = 0; b.n[i+j+k] >= f[MAXLEN]; k++) {
				b.n[i+j+k+1] += b.n[i+j+k] / f[MAXLEN];
				b.n[i+j+k] %= f[MAXLEN];
			}
		}
	*this = b;
}
void HugeInt::divide(const HugeInt& hi, int f) {
	HugeInt b = hi;
	int p = 0, i, x;
	char d[L_MAX] = { 0 }, l[90] = { 0 };
	if(compareTo(b) >= 0) {
		b <<= length - hi.length;
		p = length - hi.length;
		if(compareTo(b) >= 0) b <<= 1, p++;
	}
	if(p != 0) {
		b.div10();
		for(i = 0; i < p; i++)
			d[i] = times(b) + '0', b.div10();
	} else d[p++] = '0';
	printf("%s ", d);
	print(' ');
	for(i = 0; i < f; i++) {
		*this <<= 1;
		l[i] = times(hi) + '0';
	}
	*this <<= 1;
	x = times(hi);
	if(x >= 5) {
		if(f == 0) d[p-1]++;
		else {
			l[f-1]++;
			for(i = f-1; i > 0; i--)
				if(l[i] >= 10 + '0') l[i-1]++, l[i] -= 10;
				else break;
			if(l[0] >= 10 + '0')
				d[p-1]++, l[0] -= 10;
		}
		for(i = p-1; i > 0; i--)
			if(d[i] >= 10 + '0') d[i-1]++, d[i] -= 10;
			else break;
	}
	if(d[0] >= 10 + '0') {
		d[0] -= 10;
		putchar('1');
	}
	printf("%s", d);
	if(f != 0) printf(".%s", l);
	putchar('\n');
}
void HugeInt::print(char end) const {
	bool begin = false;
	int len, i, j;
	for(i = MAX-1; i >= 0; i--) {
		if(n[i] == 0) {
			if(begin) printf("0000");
		} else {
			if(begin) {
				len = MAXLEN - getlen(n[i]);
				for(j = 0; j < len; j++) putchar('0');
			} else begin = true;
			printf("%d", n[i]);
		}
	}
	if(!begin) putchar('0');
	putchar(end);
}

int main()
{
	char line[L_MAX], n[320], m[320], op;
	int c;
	HugeInt a, b;

	while(gets(line) != NULL) {
		sscanf(line, "%s%*[' ']%c %s %d", n, &op, m, &c);
		a.make(n); b.make(m);
		switch(op) {
		case '+': a += b; a.print('\n'); break;
		case '-':
			if(a.compareTo(b) < 0) {
				b -= a;
				putchar('-');
				b.print('\n');
			} else {
				a -= b;
				a.print('\n');
			}
		break;
		case '*': a *= b; a.print('\n'); break;
		case '/': a.divide(b, c); break;
		}
	}
	
	return 0;
}