矩阵快速幂模版

博主链接

矩阵快速幂模版

#include<bits/stdc++.h> 
using namespace std;
int N=7;
void Matrix(int (&a)[2][2],int b[2][2]){
	int tmp[2][2]={0};
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%N;
	for(int i=0;i<2;++i){
				for(int j=0;j<2;++j){
			a[i][j]=tmp[i][j];
	    }
	}
}
int main(){
	int a,b,n;
	while(scanf("%d%d%d",&a,&b,&n)){
		if(a==0&&b==0&&n==0)break;
		if(n==1){
           cout<<1<<endl;
           continue;
       		}
		int temp[2][2]={a,b,0,0},cot[2][2]={1,0,0,1}, x[2] = {1, 1};
		n-=2;
		while(n){ 
			if(n&1)Matrix(cot,temp);
			Matrix(temp,temp);
			n/=2;

		}
		int ans=0;
		for(int i=0;i<2;i++)
		ans=(ans+x[i]*cot[0][i])%N;
		cout<<ans<<endl;
	}
} 

快速幂函数

ll quick_mod(ll a,ll b,ll c) //快速幂计算(a^b)%c
{
    ll ans = 1;
    while(b)
    {
        if(b&1)   //相当于b%2==1
            ans = (ans*a)%c;
        a = (a*a)%c;
        b>>=1;    //相当于b/=2
    }
    return ans;
}