快速幂
如果要你自己写一个pow()函数，需要求2的2000000000次方，怎么求？
int pow(int a,int b){ //普通乘
int ans = 1;
for(int i=1; i<=b; i++)
ans *= a;
return ans;
}
上述代码的时间复杂度是o(n)，当数据数量级很大的时候，这份代码的耗时会非常巨大，并不能解决我们的问题。那我们该怎么办呢？
以2的74次方为例，74的二进制为1001010。对应的，我们得到74=2+8+64。
我们把问题转化为2的74次方 =2的2次方 * 2的8次方 * 2的64次方 。通过这个思路，这样我们把算法的复杂度降到了o(log n)。
void Pow(long long a,long long b) //快速幂 求a的b次幂
{
long long s=1;
while(b)
{
if(b&1) s=s*a;
a=a*a;
b>>1;
}
printf("%lld",s);
}
``
``**
矩阵快速幂
**
我们都知道斐波那契数列 ，而 F[N] =F[N-1]+F[N-2]。
显然，采用递加的方式求f[n]我们需要运算 n-1次。当数据数量级很大的时候，在有限的时间内，我们是无法答案的。那么我们该怎么办呢？
思路一：先来看斐波那契数列 ，我们先初始化三个矩阵令a[2][2]={1,1,1,0},b[2]={1,1}，c[2][1]={0}。那么是不是会有 c[0][0]=a[0][0]*b[0][0]+a[0][1]*b[1][0]=1+1=2。
c[1][0]=a[1][0]*b[0][0]+a[1][1]b[1][0]=1+0=1。
即：
乘号右侧的所有元素组成斐波那契数列的元素，我们可以用c[0][0]表示。那么我们这样做有什么好处呢？理由同快速幂，因为这样F[N]=a矩阵的n-1次方b矩阵 。这样一来 ，我们只不过是把底数换成了一个矩阵而已，利用上述的思路可以将时间复杂度大大降低。我们把矩阵a称为转移矩阵，用数组表示是[1,1,1,0]。最后的答案我们可以通过a的n-1次方获得。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n,c[2][2],d[2][2],a[2][2]={1,1,1,0},b[2][2]={1,0,0,1};
void Matrix1()
{
memset(c,0,sizeof(c));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
c[i][j]+=b[i][k]*a[k][j];
}
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
b[i][j]=c[i][j];
}
}
}
void Matrix2()
{
memset(d,0,sizeof(d));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
d[i][j]+=a[i][k]*a[k][j];
}
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
a[i][j]=d[i][j];
}
}
}
int main()
{
scanf("%d",&n);
if(n==1) printf("1");
else if(!n) printf("0");
else
{
n-=2;
while(n)
{
if(n&1) Matrix1();
Matrix2();
n>>=1;
}
printf("%d ",b[0][0]+b[0][1]);
}
return 0;
}
思路二：
参考思路：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n,c[2][2],d[2][2],a[2][2]={1,1,1,0},b[2][2]={1,0,0,1};
void Matrix1()
{
memset(c,0,sizeof(c));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
c[i][j]+=b[i][k]*a[k][j];
}
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
b[i][j]=c[i][j];
}
}
}
void Matrix2()
{
memset(d,0,sizeof(d));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
d[i][j]+=a[i][k]*a[k][j];
}
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
a[i][j]=d[i][j];
}
}
}
int main()
{
scanf("%d",&n);
while(n)
{
if(n&1) Matrix1();
Matrix2();
n>>=1;
}
printf("%d ",b[0][1]);
return 0;
}
如有不妥，欢迎指正。