【hdoj_1715】大菲波数(大数+100000000进制)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1715

本题采用大数加法即可解决.采用100000000进制速度更快.

C++代码如下：

#include<iostream>
#include<string.h>
using namespace std;

#define maxn 1000 + 1//最多算到f(1000)
#define len 1000//结果最多有1000*8位
int a[maxn][len];

int main()
{
	int i,j;
	for(i=1;i<maxn;i++)
		memset(a[i],0,sizeof(a[i]));

	a[1][len-1] = 1;//f(1)
	a[2][len-1] = 1;//f(2)

	for(i=3;i<maxn;i++)//从3开始,计算f(i)
	{
		int c = 0;
		for(j=len-1;j>=0;j--)
		{
			c += (a[i-1][j]+a[i-2][j]);
			a[i][j] = c % 100000000;//100000000进制
			c /= 100000000;
		}
	}

	int T,n;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n<=2)
			printf("%d
",1);
		else
		{
			for(i=0;i<len;i++)
				if(a[n][i])
					break;
			printf("%d",a[n][i]);
			for(j=i+1;j<len;j++)
				printf("%08d",a[n][j]);//针对100000000进制的输出方式 "%08d"
			printf("
");
		}
	}

	return 0;
}

上述代码，提交可以通过.耗时约为15ms或31ms.