矩阵乘方(递归，java）

 问题描述
　　给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。
　　其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。
　　要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。下面给出一种较快的算法(用A^b表示A的b次方)：
　　若b=0，则A^b%m=I%m。其中I表示单位矩阵。
　　若b为偶数，则A^b%m=(A^(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。
　　若b为奇数，则A^b%m=(A^(b-1)%m)*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。
　　这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2x2的矩阵，m不大于10000。
输入格式
　　输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。
输出格式
　　输出两行，每行两个整数，表示A^b%m的值。
样例输入
2 2
1 1
0 1
样例输出
1 0
0 1
 

import java.util.Scanner;

public class Main {
	static int m;
	public static void main(String []args) {
		Scanner in=new Scanner(System.in);
		int b=in.nextInt();
		m=in.nextInt();
		int a[]=new int[5];
		int t[]=new int[5];
		for(int i=1;i<=4;i++)
			a[i]=in.nextInt();
		mul(a,b);

		System.out.printf("%d %d\n",a[1],a[2]);
		System.out.printf("%d %d\n",a[3],a[4]);
		
	}
	public static void mul(int a[],int b) {
		if(b==0) {
			a[1]=1%m;
			a[2]=0%m;
			a[3]=0%m;
			a[4]=1%m;
		}else if(b%2==0) {
			mul(a,b/2);
			sol(a,a);
		}else {
			int t[]=new int[5];
			for(int i=1;i<=4;i++)
				t[i]=a[i];
			mul(a,b-1);
			sol(a,t);
		}
	}
	public static void sol(int []a,int []t) {
		int t1=a[1]*t[1]+a[2]*t[3];
		int t2=a[1]*t[2]+a[2]*t[4];
		int t3=a[3]*t[1]+a[4]*t[3];
		int t4=a[3]*t[2]+a[4]*t[4];
		a[1]=t1%m;
		a[2]=t2%m;
		a[3]=t3%m;
		a[4]=t4%m;
	}
	

}