2014.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

#include <cstdio>
#define  CARRY  100000000

class BigInt {
private:
	int getLength(long n) {
		int len;
		for(len = 0; n > 0; len++) {
			n /= 10;
		}
		return len;
	}
public:
	long num[20];
	BigInt(BigInt *a, BigInt *b) {
		int i;
		for(i = 0; i < 20; i++) {
			num[i] = 0;
		}
		add(a, b);
	}
	BigInt(long n) {
		int i;
		num[0] = n;
		for(i = 1; i < 20; i++) {
			num[i] = 0;
		}
	}
	void add(BigInt *a, BigInt *b) {
		int i;
		for(i = 0; i < 20; i++) {
			num[i] += a->num[i] + b->num[i] * 2;
			if(num[i] >= CARRY) {
				num[i+1] = num[i] / CARRY;
				num[i] %= CARRY;
			}
		}
	}
	void print() {
		bool havePrint = false;
		int i, j, len;
		for(i = 19; i >= 0; i--) {
			if(num[i] != 0) {
				len = 8 - getLength(num[i]);
				if(havePrint) {
					for(j = 0; j < len; j++) {
						putchar('0');
					}
				}
				printf("%ld", num[i]);
				havePrint = true;
			} else {
				if(havePrint) {
					printf("00000000");
				}
			}
		}
		putchar('\n');
	}
};

int main()
{
	BigInt *c[251];
	int i, n;
	
	c[0] = new BigInt(1);
	c[1] = new BigInt(1);
	for(i = 2; i < 251; i++) {
		c[i] = new BigInt(c[i-1], c[i-2]);
	}
	while(scanf("%d", &n) == 1) {
		c[n]->print();
	}
	
	return 0;
}