幂乘 - 快速幂

幂乘

通常情况下我们都是这样来写的：

int n, m, ans=1;
cin>>m>>n;
for(int i=1; i<=n; i++)
	ans *= m;
cout<<ans<<endl;

或者是用cmath库中的pow函数

函数原型：

double pow(double x,double y);

朴素的算法（包括pow()函数）就是for循环，一遍一遍M*M*M*M*……时间复杂度O(N)。

当然 免不了TLE警告。

对于某些变态数据，肯定是不够的，就需要用一些方法加速幂运算。

快速幂

由于幂运算的性质，。

因此对于，利用二进制思想，转化为

用公式整理一下：

代码实现：

int quick_pow(int a, int b)
{
    int rslt = 1;
    while(b)
    {
        if(b & 1) rslt *= a;
        a *= a;
        b >>= 1;
    }
    return rslt;
}

或

int quick_pow(int a, int b)
{
    int rslt = 1;
    for(int i=0; i<n; i++)
    {
        if((1 << i) & b) rslt *= a;
        a *= a;
    }
    return rslt;
}

快速幂取模

淘的以前的老代码。。

反正都一样啦

#include<cstdio>
long long mi(long long a,long long b,long long p)//a^b%p
{
	a%=p;//防止a大于p，对a进行预处理 
	long long now=a,ans=1;//a^(2^0)  1
	while(b)//b%2 
	{
		if(b&1) ans=ans*now%p;
		now=now*now%p;
		b>>=1;
	}
	return ans;
} 
int main()
{
	long long a,b,p,c;
	scanf("%I64d%I64d%I64d",&a,&b,&p);
	c=mi(a,b,p);
	printf("%I64d",c);
	return 0;
}

矩阵快速幂

首先线性代数矩阵乘法要会。

矩阵的幂乘就是算A^n，方法很简单，把快速幂算法中的乘法改成矩阵的乘法就可以了。

const int N=10;
int tmp[N][N];
void multi(int a[][N],int b[][N],int n)
{
    memset(tmp,0,sizeof tmp);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        for(int k=0;k<n;k++)
        tmp[i][j]+=a[i][k]*b[k][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        a[i][j]=tmp[i][j];
}
int res[N][N];
void Pow(int a[][N],int n)
{
    memset(res,0,sizeof res);//n是幂，N是矩阵大小
    for(int i=0;i<N;i++) res[i][i]=1;
    while(n)
    {
        if(n&1)
            multi(res,a,N);//res=res*a;复制直接在multi里面实现了；
        multi(a,a,N);//a=a*a
        n>>=1;
    }
}

res数组就等同于普通快速幂初始化的1，原理相通，这个矩阵叫单位矩阵E,性质就是E*A=A,就是1*a=a，一样，单位矩阵就是对角线全是1其他全是0。

最终得出一个res矩阵。

矩阵快速幂的应用：https://blog.csdn.net/wust_zzwh/article/details/52058209

 

相关练习题：

快速幂取模       库特的数学题       矩阵快速幂       快速幂||取余运算

https://me.csdn.net/baidu_41248654