快速幂模板

以下代码输入a, b, p。会输出a的b次方再取余p。

注：快速幂思想在矩阵相乘时依然可用

递归版

int power(int a, int b, int p) {//a^b%p
    if (!b) return 1;
    long long t = power(a, b>>1, p);
    if (b % 2 == 0) t = t * t % p;
    else t = t * t * a % p;
    return t;
}

 非递归版

int power(int a,int b,int mo){//a^b%mo
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mo;
        a=1ll*a*a%mo;
        b>>=1;
    }
    return ans;
}

 矩阵快速幂

#define maxn 2
#define mo 1000000007
struct Matrix{
    long long a[maxn][maxn];
    Matrix(){
        memset(a,0,sizeof(a));
    }
    Matrix operator * (const Matrix& c)const{
        Matrix b;
        for(int i=0;i<maxn;i++){
            for(int j=0;j<maxn;j++){
                for(int k=0;k<maxn;k++){
                    b.a[i][j]+=a[i][k]*c.a[k][j];
                    b.a[i][j]%=mo;
                }
            }
        }
        return b;
    }
}a;
Matrix power(Matrix a,long long b){//a^b%mo
    Matrix ans;ans.a[0][0]=ans.a[1][1]=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a,b>>=1;
    }
    return ans;
}