本文主要是介绍快速幂/快速幂取模/矩阵求解快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
因为做了一个Fibonacci的题需要用矩阵+快速幂求解所以引发了下面一系列问题！！！
快速幂：
快速幂时间复杂度为 O(log2N)， 与朴素的O(N)相比效率有了极大的提高。
例如：
代码：
#include <stdio.h>
int power(int n, int k)
{int ans = 1;while( k ){if(k&1)ans *= n ;k= k/2;n *= n;}return ans ;
}
int main ( )
{int n, k;while(scanf("%d %d",&n, &k)!=EOF){printf("%d\n",power(n,k));}
}快速幂取模：
快速幂取模还不算太懂，只知道需要对每一个值取模，公式 a*b%c=((a%c)*b)%c 。
代码：
#include<stdio.h>
int main()
{long long a,b,c,d;int T;scanf("%d",&T);while(T--){scanf("%lld%lld%lld",&a,&b,&c);long long ans=1;while( b ){if( b%2 )ans = ( ans * a ) % c;b/=2;a = ( a * a ) % c;}printf("%lld\n",ans);}return 0;
}
矩阵+快速幂 求解Fibonacci数列：
矩阵：矩阵可以看成一个n×m的数表，用二维数组表示
矩阵乘法：定义矩阵A,B。A和B可以乘法操作当且仅当A的大小是a×b，B的大小是b×c，设矩阵C=AB，则C的大小是a×c，
且有：
最普通的矩阵乘法是直接三个for循环直接计算而已，所以复杂度是O（n3）.
运用矩阵乘法快速幂，可以快速计算出矩阵B^(n-1),这样实现将时间复杂度降低到O(log n).
代码（nyoj 698题 A Coin Problem 别人优代码 ）：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
const int Max = 10000;
struct M
{long long p[2][2];
};
M mult(M a,M b)
{int i,j,k;M c;for(i=0;i<2;i++)for(j=0;j<2;j++){c.p[i][j]=0;for(k=0;k<2;k++){c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%Max)%Max;}}return c;
}
M pow(M a,long long k)
{M b={1,0,0,1};while(k){if(k&1)b=mult(b,a);a=mult(a,a);k>>=1;}return b;
}
int main()
{int t;long long n;scanf("%d",&t);while(t--){scanf("%lld",&n);M a={1,1,1,0};M c;c=pow(a,n-1);printf("%lld\n",(c.p[0][0]*2+c.p[0][1]*1)%Max);}return 0;
}
还不明白请点击~>
这篇关于快速幂/快速幂取模/矩阵求解快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
