快速幂及矩阵快速幂

快速幂

#include<stdio.h>  
#define ll long long  
ll FastPower(ll a,ll b,int mod);  
int main()  
{  

        ll a, b , mod; 
          
        scanf("%lld %lld %lld",&a,&b,&mod);
        long long res = FastPower(a,b,mod);				//res为a ^ b % mod  的结果 
        printf("%lld\n",res);
    
      
      
      
    return 0;  
}   
ll FastPower(ll a,ll b,int mod)  
{  
    ll result=1;  
    while(b)  
    {  
        if(b&1)  
        result = (result * a) % mod;  
        b>>=1;  
        a = (a * a) % mod;   
    }  
    return result;  
      
}  

矩阵快速幂

详解点击打开链接

？

#include<algorithm>
#include<stdio.h>
#include<string.h> 
#define ll long long
using namespace std;
const ll Mod =1000000009;
struct Mat
{
	int n, m;
	
	ll data[4][4];
};

Mat ans;

Mat MatMul(Mat a, Mat b);

Mat MatMod(Mat a, ll mod);		//矩阵取模 

Mat MatFastPoswer(Mat a, ll k, ll mod);

int main()
{
	
	int n,m;
	scanf("%d %d",&n, &m);		//输入矩阵的行数和列数
	
	Mat data;
	data.n = n;
	data.m = m;
	for(int i = 1; i <= n; i++)			//输入矩阵。 
	{
		for(int j = 1; j <= m; j++)
		scanf("%lld",&data.data[i][j]);
	} 
	ll k;						//幂次
	ll mod;
	scanf("%lld %lld",&k, &mod) ;
	
	Mat result = MatFastPoswer(data, k ,mod);
	
	for(int i = 1; i <= result.n; i++)			//输出矩阵 
	{
		for(int j = 1; j <= result.m; j++)
		printf("%lld ",result.data[i][j]) ;
		printf("\n");	
	}
	
	
	return 0;
}

Mat MatFastPoswer(Mat a, ll k, ll mod)
{
	int maxn = max(a.n,a.m);
	
	ans.n =  ans.m = maxn;
	
	memset(ans.data, 0 , sizeof(ans.data));
	for(int i =1; i <= ans.n; i++)
	ans.data[i][i] = 1;
	
	Mat res;
	res = a;
	while(k)
	{
		if(k & 1)
		ans = MatMod(MatMul(ans,res), mod);
		
		res = MatMod(MatMul(res, res), mod);
		
		k = k >> 1;
	}
	
	
	
	return ans;
	
}

Mat MatMul(Mat a, Mat b)
{
	Mat temp ;
	
	temp.n = a.n, temp.m = b.m;
	
	for(int i = 1; i <= temp.n; i++)
	{
		for(int j =1; j <= temp.m; j++)
		{
			temp.data[i][j] = 0;
			
			for(int k = 1; k <= temp.m; k++)
			{
				temp.data[i][j] += (a.data[i][k] * b.data[k][j]);
			}
		}
	}
	return temp;
}
Mat MatMod(Mat a, ll mod)
{
	Mat temp = a; 
	
	for(int i = 1; i <= temp.n; i++)
	{
		for(int j = 1; j <= temp.m; j++)
		{
			temp.data[i][j] %= mod;
		}
	}
	
	return temp;
}