>      
> #include <string>
> #include <cstdio>
> using namespace std;
> 
> 
> const int MAX = 1000001;
> char w[MAX][80];
> int l[MAX];
> 
> 
> int str_add(char *a, char *b, char *c1)
> {
> 	char *c;
> 	int p, q;
> 	int i, j;
> 	int tmp;
> 	bool flag;
> 	c = new char[100]; 
> 	p = strlen(a)-1;
> 	q = strlen(b)-1;
> 	flag = false;
> 	j = 0;
> 	while (q >= 0) {
> 		tmp = a[p--] + b[q--] - 96;
> 		if (flag) {
> 			tmp++;
> 		}
> 		flag = false;
> 		if (tmp >= 10) {
> 			tmp -= 10;
> 			flag = true;
> 		}
> 		c[j++] = char(tmp+48);
> 	}
> 	while (p >= 0) {
> 		tmp = a[p--] - 48;
> 		if (flag) {
> 			tmp++;
> 		}
> 		flag = false;
> 		if (tmp >= 10) {
> 			tmp -= 10;
> 			flag = true;
> 		}
> 		c[j++] = char(tmp+48);
> 	}
> 	if (flag) {
> 		c[j++] = '1';
> 	}
> 	c[j] = '\0';
> 	j = 0;
> 	for (i=strlen(c)-1; i>=0; i--) {
> 		c1[j++] = c[i];
> 	}
> 	c1[j] = '\0';
> 	return 0;
> }
> 
> 
> 
> int main()
> {
> 	int n;
> 	int i, j, k;
> 	int len;
> 	char out[10];
> 
> 
> 	strcpy(w[1], "1");
> 	strcpy(w[2], "2");
> 	
> 	l[1] = 1;
> 	l[2] = 2;
> 
> 	for (i=3; i<MAX; i++)
> 	{
> 		if (i%2 == 1) 
> 			strcpy(w[i], w[i-1]);
> 		else
> 		    str_add(w[i-2], w[i/2], w[i]);
> 
> 		len = strlen(w[i]);
> 		j = 0;
> 		if (len >= 10)
> 		{
> 			j = len - 9;	
> 		}
> 		l[i] = atoi(w[i]+j);
> 	}
> 	
> 	while (scanf("%d", &n) != EOF)
> 	{	
> 		printf("%d\n", l[n]);
> 	}
> 	return 0;
> }

不用高精度 递推的时候mod 1000000000就行