求n^m 时间复杂度log(m)的算法

 

 

非常好用，在此先分享给大家~

 

求n^m 时间复杂度log(m) int calc(int n,int m){ int re=1; while(m){ if(m&1) re*=n; n*=n; m>>=1; } return re; } 求矩阵[n]^m 时间复杂度log(m) #include<cstring> #include<iostream> using namespace std; #define N 2 #define MOD 10000 struct Matrix { int m[2][2]; }; void matrixMultiplication(Matrix &res,int n) { Matrix tm,tm1; int i,j,k; tm=res; for (i=0;i<N;i++) for (int j=0;j<N;j++) { res.m[i][j]=(i==j); } if(n==0){ return; } while(n) { if(n&1) { memset(tm1.m,0,sizeof(tm1.m)); for (i=0;i<N;i++) { for (j=0;j<N;j++) { for(k=0;k<N;k++) { tm1.m[i][j] += (res.m[i][k]*tm.m[k][j])%MOD; tm1.m[i][j] %= MOD; } } } res=tm1; } memset(tm1.m,0,sizeof(tm1.m)); for (i=0;i<N;i++) { for (j=0;j<N;j++) { for(k=0;k<N;k++) { tm1.m[i][j] += (tm.m[i][k]*tm.m[k][j])%MOD; tm1.m[i][j] %= MOD; } } } tm=tm1; n>>=1; } }