快速幂和矩阵快速幂

1、快速幂 快速幂的目的就是做到快速求幂，假设我们要求a^b，那么其实b是可以拆成二进制的，该二进制数第i位的权为(i-1)，例如当b==11时，a¹¹=a¹+a²+a⁸，代码如下：

#include <cstring> #include <string> #define LL long long #define MAX(a,b) (a)>(b)?(a):(b) #define MIN(a,b) (a)<(b)?(a):(b) using namespace std; //快速幂非递归版 LL quick( LL a, LL pow ) { LL ans = 1; while ( pow > 0 ) { if( pow&1 ) ans = ans * a; a = a * a; pow >>= 1; } return ans; } //快速幂递归版 LL Quick( LL a, LL b) { if( b == 1 ) return a; LL ans = Quick(a, b>>1); if( b&1 ) return ans * ans * a; else return ans * ans; } LL quickmod( LL a, LL b, int mod) { int ans = 1; while ( b > 0 ) { if( b&1 ) ans = ( (ans%mod) * (a%mod) ) % mod; a = ( (a%mod) * (a%mod) ) % mod; b >>= 1; } return ans; } int main() { LL a, b; a = 3; b = 344; printf("%lld\n", quick(a, b)); printf("%lld\n", Quick(a,b)); printf("%d\n", quickmod(a,b,10)); return 0; }

2、矩阵快速幂 参见博文

3、矩阵乘法快速幂优化递推序列 参加博文添加链接描述