nyist 148 fibonacci數列的矩陣解法

用二分冪進行矩陣乘法運算。

#include <iostream>
using namespace std;
int f(int n)
{
	if(n==0||n==1) return n;
	int a2=1,a1=1,a0=0,f2=1,f1=0,f0=1,p2,p1,p0; n--;
	if(n==1) return a2;
	while(n)
	{
		if(n%2) 
		{
		p2=f2*a2+f1*a1,p1=f2*a1+f1*a0,p0=f1*a1+f0*a0;
		f2=p2%10000,f1=p1%10000,f0=p0%10000;
		}
		p2=a2*a2+a1*a1; p1=a2*a1+a1*a0; p0=a1*a1+a0*a0;
		a2=p2%10000,a1=p1%10000,a0=p0%10000;
		n/=2;
	}
	return f2;
}
int main(int argc, char *argv[])
{
	int n;
	while(cin>>n&&(n!=-1))
	{
		cout<<f(n)<<endl;
	}
	return 0;
}