学步园

1.当n大于40时，前四位可以用fibonacci的公式来求，后四位用矩阵乘法来求

代码：

#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;

const double a=(1+sqrt(5.0))/2;

struct node 
{
	int matrix[3][3];
}ma,e;
node operator *(node x,node y)
{
	node temp;
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
		{
			temp.matrix[i][j]=0;
			for(int k=1;k<=2;k++)
				temp.matrix[i][j]+=x.matrix[i][k]*y.matrix[k][j];
			temp.matrix[i][j]=temp.matrix[i][j]%10000;
		}
	return temp;
}
node operator ^(node x,int k)
{
	node ans=e,p=x;
	while(k)
	{
		if(k&1)
		{
			ans=ans*p;
		}
		k=k/2;
		p=p*p;
	}
	return ans;
}
int main()
{
	int arr[41];
	arr[0]=0;
	arr[1]=1;
	for(int i=2;i<=40;i++)
		arr[i]=arr[i-1]+arr[i-2];
	int n;
	ma.matrix[1][1]=ma.matrix[1][2]=ma.matrix[2][1]=e.matrix[1][1]=e.matrix[2][2]=1;
	ma.matrix[2][2]=e.matrix[1][2]=e.matrix[2][1]=0;
	
	
	while(scanf("%d",&n)!=EOF)
	{
		if(n<40)
			printf("%d\n",arr[n]);
		else
		{
		    node t=ma^(n-1);
			int ans2=t.matrix[1][1]%10000;

            double temp=(   log10(1/sqrt(5.0))+n*log10(a)  );
			temp=temp-(int)temp;
			temp=pow(10.0,temp);
			while(temp<1000)
			   temp=temp*10;
			printf("%d...",(int)temp);
			printf("%.4d\n",ans2);
		}
	}
	system("pause");
	return 0;
}