【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\n",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("\n");

		}

	}

	return 0;

}

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

巴特西

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

最新文章

热门文章