POJ3070Fibonacci 矩阵快速幂

POJ3070原题
http://poj.org/problem?id=3070


如图，Fibonacci矩阵解法：

import java.util.Scanner;

public class Main
{
	Scanner scan=new Scanner(System.in);
	long n;
	int w=10000;
	long[][] a=new long[2][2];
	public static void main(String[] args)
	{
		new Main().run();
	}
	
	long[][] multi(long[][] b,long[][] a)
	{
		long[][] c=new long[2][2];
		for(int i=0;i<b.length;i++)
		{
			for(int j=0;j<a[i].length;j++)
			{
				for(int k=0;k<a.length;k++)
				{
					c[i][j]=(c[i][j]+b[i][k]*a[k][j])%w;
				}
			}
		}
		return c;                    
	}
	void evaluate()//初始化矩阵
	{
		a[0][0]=a[0][1]=a[1][0]=1;
		a[1][1]=0;

	}

//矩阵快速幂
	long fastpow(long[][] a,long n)
	{
		long[][] b=new long[2][2];
		b[0][0]=b[1][1]=1;
		b[0][1]=b[1][0]=0;
		while(n>0)
			{
				if(n%2==1)
					b=multi(b,a);
				a=multi(a,a);
				n>>=1;//右移一位表示除2
			}
			return b[0][1];
	}
	void run()
	{
		while(true)
		{
			n=scan.nextLong();
			if(n==-1)
				break;
			else{
				evaluate();
				long c=fastpow(a,n);
				System.out.println(c);
			}
		}
	}
}