快速幂和矩阵快速幂

跟着罗勇军老师学习所得

判断奇偶

推荐使用位运算判断奇偶

取模运算：n%2==1   奇数n%2==0   偶数位运算：n&1==1  奇数n&1==0  偶数

分治法求幂

int fastPow(int a,int n){if(n==1)return a;int temp=fastPow(a,n/2);if(n&1==1)return temp*temp*a;elsereturn temp*temp;} 

快速幂

int fastPow(int a,int n){     //计算a的n次方int ans=1;      //用ans返回结果while(n){      //整数n就直接是二进制数，不需要转换if(n&1) //如果最后一位是1return ans=ans*a;   a=a*a;n=n>>1;}return ans;}

需要进行取模运算
return ans=ans*a % mod;
return ans%mod;
这个mod可以是任意数

例题

求2022^{1000000000000}的后四位

#includeusing namespace std;const int mod=10000;int fastPow(int a,long long n){     //计算a的n次方int ans=1;      //用ans返回结果while(n){      //整数n就直接是二进制数，不需要转换if(n&1) //如果最后一位是1return ans=ans*a % mod;   a=a*a %mod;n=n>>1;}return ans % mod;}int main(){cout<<"ans="<<fastPow(2022,1000000000000)<<endl;}

a=a*a %mod;
一定要在这里加个取模否则会溢出

矩阵快速幂

重载矩阵乘法

struct matrix{int m[N][N];}matrix operation * (const matrix&a,const matrix&b){matrix c;memset(c.m,0,sizeof(c.m));    //清零for(int i=0;i<N;i++){for(int j=0;j<N;j++){for(int k=0;k<N;k++){c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]);}}}return c;}

快速幂(和数的快速幂并没有太多区别)

matrix pow_matrix(matrix a,int n){matrix ans;memset(ans.m,0,sizeof(ans.m));for(int i=0;i<N;i++)ans.m[i][i]=1;    //初始化为单位矩阵while(n){if(n&1)ans=ans*a;a=a*a;n=n>>1;}return ans;}