fib.cpp

利用矩阵乘法和二进制快速计算菲波拉契数列第n项

#include<iostream>
#include<fstream>
using namespace std;
#define MAXLEN 28
#define m 900

struct mat
{
	int _11,_12,_21,_22;
};

int n,i,len;
bool bin[MAXLEN];
mat ms[MAXLEN];

//矩阵乘法
mat matmul(int a,int b)
{
	mat c;
	c._11=((ms[a]._11*ms[b]._11)%m+(ms[a]._12*ms[b]._21)%m)%m;
	c._12=((ms[a]._11*ms[b]._12)%m+(ms[a]._12*ms[b]._22)%m)%m;
	c._21=((ms[a]._21*ms[b]._11)%m+(ms[a]._22*ms[b]._21)%m)%m;
	c._22=((ms[a]._21*ms[b]._12)%m+(ms[a]._22*ms[b]._22)%m)%m;
	return c;
}

int main()
{
	//计算M^(2^i)
	ms[1]._11=ms[1]._12=ms[1]._21=1;
	ms[1]._22=0;
	for(i=2;i<=MAXLEN;++i)
	{
		ms[i]=matmul(i-1,i-1);
	}
	//读入
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
		{
			break;
		}
		//将n转为二进制
		len=0;
		while(n!=0)
		{
			len++;
			bin[len]=(n%2==0)?false:true;
			n>>=1;
		}
		//ms[0]保存结果,初值为单位阵
		ms[0]._11=ms[0]._22=1;
		ms[0]._12=ms[0]._21=0;
		for(i=1;i<=len;++i)
		{
			if(bin[i])
			{
				ms[0]=matmul(0,i);
			}
		}
		printf("%d\n",ms[0]._12);
	}
	return 0;
}