蓝桥杯算法提高VIP-矩阵乘方 （C语言代码）

解题思路: 递归

注意事项:

参考代码:

#include<iostream>
using namespace std;
int a[2][2];
int b, m;
int sum; 
void mul(int e[][2], int d[][2], int m)
{
//  cout<<"调用乘法"<<endl;
	int c[2][2];
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			sum=0;
            for(int k=0; k<2; k++)
                sum+=e[i][k]*d[k][j];
            c[i][j]=sum % m;
		}
	}
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			a[i][j] = c[i][j];
		} 
	}
	return ;
} 
void fun(int a[][2], int b, int m)
{
	if(b == 0)
	{
//		cout<<"调用1"<<endl; 
		for(int i = 0; i < 2; i++)
		{
			for(int j = 0; j < 2; j++)
			{
				if(i == j)
				   a[i][j] = 1%m;
				else
				   a[i][j] = 0;	
			}
		}
		return ;
	}
	if(b%2==1)
	{
//		cout<<"调用2"<<endl; 
		int c[2][2];
		for(int i = 0; i < 2; i++)
		{
		    for(int j = 0; j < 2; j++)
			{
				c[i][j] = a[i][j];
			} 
		}
        fun(a,b-1,m);
        mul(a,c,m); 
        return ;
	}
	else
	{
//		cout<<"调用3"<<endl; 
		fun(a,b/2,m);
		mul(a,a,m);
		return ;
	}
	return;
}
int main()
{
	cin>>b>>m;
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			cin>>a[i][j];
		}
	}
	fun(a, b, m); 
	for(int i = 0; i < 2; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			cout<<a[i][j]<<' ';
		} 
		cout<<endl;
	}
	return 0;
}