快速幂

所谓的快速幂，其目的是为了快速求幂，将时间复杂度从O（n）朴素算法的降到O（logn）。

假如现在要求a^b，按照朴素算法，就是将a连乘b次，时间复杂度为O(b)，即O（n）级别。

a^b的朴素算法

// O(n)
#include<cstdio>
// a^b的朴素算法
int pow(int a,int b)
{
    int ans=1;
    while(b)
    {
          ans*=a;
          b--;
    }
    return ans;
}

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%dn",pow(a,b));
}

快速幂的原理

还是原来的a^b，我们会发现，其实指数b是可以拆成二进制的。通过式子a^(m+n) =(a^m )* (a ⁿ)，我们可以发现，一旦指数b拆成二进制，那么a^b也可以进行相应的拆分。
例如，当b=11时，b的二进制为1011，即11 = 1*(2⁰) +1*(2¹) + 1*(2³)。则a¹¹ = a^ (1*(2⁰) +1*(2¹) + 1*(2³)) =(a¹) * (a²) *(a³)， 可以看到通过二进制转换，我们只需要进行3次计算，而用朴素算法我们需要进行11次计算。

接着就是如何判断一个数在二进制形式的某个位置是0还是1，以及具体的代码实现了。

因为是二进制，我们很容易联想到位运算，这里我们需要用到与运算&和右移运算>>。

• · &运算：通常用于二进制取位操作，例如一个数x & 1的结果就是取二进制的最末位的值。还可以判断这个数的奇偶性，如果x&10，则x为偶数；如果x&11，则x为奇数。
• · >>运算：在这里是作为除法来使用，例如一个数x，x >> 1就表示x右移一位，即x=x/2。注意： 移位符号右侧的整数表示的是2的幂
• · << : 左移运算符，num << 1,相当于num乘以2,表示加0。
• · >>> : 无符号右移,也叫逻辑位移，忽略符号位，空位都以0补齐

快速幂【代码】

//【快速幂】 
#include<cstdio>
#include<iostream>
using namespace std;
// 快速幂的核心代码
int pow(int a,int b)
{
    int ans=1,base=a;// ans：幂的结果；base：底数a
    while(b)
    {
        if(b & 1)
        {
        ans=ans*base;
        }
        base=base*base;
        b = b >> 1;
    }
    return ans;
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("结果：%dn",pow(a,b));
}

快速幂取模

所谓的快速幂取模，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。下面我们以(a^b) mod c为例。

幂取模的朴素的实现

int pow_mod(int a,int b,int c)
{
    int ans = 1;
    for(int i = 1;i <= b;i++)
    {
       ans = ans * a;
    }
    ans = ans % c;
    return ans;
}

缺点：这个方法存在着明显的问题，如果a和b过大，很容易就会溢出。

快速幂取模原理

我们知道，模运算与基本四则运算类似，具体如下图：

这里用第四条公式：(a^b)mod c = (a mod c)^b mod c，由公式可以看出先让a关于c取余，这样可以大大减少a的大小。

快速幂取模【代码】

方法一

int pow_mod(int a,int b,int c)
{
    int ans = 1;
    a = a % c; //加上这一句
    for(int i = 1;i <= b;i++)
    {
       ans = ans * a;
    }
    ans = ans % c;
    return ans;
}

既然某个因子取余之后相乘再取余保持余数不变，那么新算得的ans也可以进行取余，所以得到比较良好的改进版本。积的取余等于取余的积的取余。
方法二

int pow_mod(int a,int b,int c)
{
    int ans = 1;
    a = a % c; //加上这一句
    for(int i = 1;i <= b;i++)
    {
       ans = (ans * a)%c;// 这里再取一次余
    }
    ans = ans % c;
    return ans;
}

以上方法的时间复杂度均为O（n），在c过大的条件下，很容易超时。因此，我们需要用到快速幂取模来降低时间复杂度。

方法三
快速幂取模算法依赖于以下明显的公式：

// time：O(logN)
// 这里不考虑指数为负数的情况
int pow_mod(int a,int b,int  c)  
{
    int ans = 1,base=a;// ans：结果；base：底数
    base = base % c;
    //【考虑0次方的情况】
    if(b==0)
    {
        return 1%c;// 任意a的0次幂都是1,故直接用1%c即可 
    } 
    while(b)
    {   
        if(b & 1) // 与运算，判断奇偶性
        ans = (ans*base) % c; 
        b = b >> 1;// 右移一位，相当于除2
        base = (base * base) % c; 
    } 
    return ans;
} 

矩阵快速幂

矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素算法的O（n）的时间复杂度，降到O（logn）。
一般求一个矩阵的n次方，我们会通过连乘n-1次来得到它的n次幂。（朴素算法）但做下简单的改进就能减少连乘的次数，方法如下：
把n个矩阵进行两两分组，比如：A * A * A * A* A * A=(AA)(AA)(AA)，这样变的好处是，你只需要计算一次AA然后将结果A*A连乘自己两次就能得到A^6，算一下发现这次一共乘了3次，少于原来的5次。

我们还可以取A^3作为一个基本单位。原理都一样：利用矩阵乘法的结合律，来减少重复计算的次数。

以上都是取一个具体的数来作为最小单位的长度，这样做虽然能够改进效率，但缺陷也是很明显的，取个极限的例子（可能有点不恰当，但基本能说明问题），当n无穷大的时候，你现在所取的长度其实和1没什么区别。

所以就需要我们找到一种与n增长速度”相适应“的”单位长度“，那这个长度到底怎么去取呢？？？这点是我们要思考的问题。既然要减少重复计算，那么就要充分利用现有的计算结果！怎么充分利用计算结果呢？？？这里考虑二分的思想。。

我们首先要认识到这一点：任何一个整数N，都能用二进制来表示。（又是二进制，可见其重要性）；我们可以将指数用二进制表示。比如A¹⁸ = （A¹⁶）*（A²），因为18 (10)=10010（2）,显然采取这样的方式计算时因子数将是log（n）级别的（原来的因子数是n）。不仅这样，因子间也是存在某种联系的，比如A⁴可以通过两个A²相乘得到，A⁸可以通过两个A⁴相乘得到，类似更高介，这点也充分利用了现有的结果作为有利条件。

矩阵快速幂【代码】

// 将二维数组放入一个结构体中
struct Mat
{
    int mat[105][105];// 具体二维数组大小视具体情况而定
};

// 重载*运算符 
// 矩阵A、B均为n阶方阵
Mat operator*(Mat A,Mat B)
{
    Mat temp;
    //memset(temp.mat,0,sizeof(temp.mat));// 将矩阵置0【零矩阵】 
    for(int i =0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ;j++)
        {
            temp.mat[i][j]=0;// 在这里将矩阵temp置零【零矩阵】
            for(int k = 0 ;k < n ;k++)
            {
                temp.mat[i][j] = (temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
            }
        }
    }
    return temp;// 返回矩阵A*B的结果 
}

// 重载^运算符 
Mat operator^(Mat A, k)
    Mat base;
    // 将矩阵base置为单位矩阵【单位矩阵】 
    for(int i=0;i<n;i++) base.mat[i][i]=1;
    // 快速幂【核心代码】 
    while(k)
    {
        if(k & 1) base = base * A;
        A = A * A;
        k = k >> 1; 
    }
    return base;
}

例题

P1226 【模板】快速幂||取余运算

输入输出样例
输入样例#1：
2 10 9
输出样例#1：
2^10 mod 9=7

//【快速幂取模】 
//用时: 21ms / 内存: 792KB
#include<iostream>
#include<cstdio>
using namespace std;

// a的b次方对c取模
// 注意类型要用long long
// 取模运算【(a*b)%c == ((a%c)*(b%c))%c】
long long pow_mod(long long a,long long b,long long  c)  
{
    long long ans = 1,base=a;
    base = base % c;
    //【考虑0次方的情况】【坑点，最后一组数据WA】
    // 数据：1^0 % 1；结果：0。
    if(b==0)
    {
        return 1%c;// 任意a的0次幂都是1,故直接用1%c即可 
    } 
    while(b)
    {   
        if(b & 1)ans = (ans*base) % c; 
        b = b >> 1;
        base = (base * base) % c; 
    } 
    return ans;
} 

long long a,b,mod;// 注意类型 
int main()
{
    scanf("%lld%lld%lld",&a,&b,&mod);
    long long result=pow_mod(a,b,mod); 
    printf("%lld^%lld mod %lld=%lldn",a,b,mod,result);// 注意输出格式
}

P3390 【模板】矩阵快速幂

输入输出样例
输入样例#1：
2 1
1 1
1 1
输出样例#1：
1 1
1 1

// 利用快速幂的思想,根据矩阵的结合律,可以递归二分求解
//【矩阵快速幂】 
#include<iostream>
#include<cstdio>
#include<cstring> //包含memset函数
using namespace std;

long long mod=1e9+7;
long long n,k;// 注意类型要为long long，不然全部WA
// 结构体存一个二维数组(矩阵)，可以直接return出来【一点好处】
struct Mat
{
    long long mat[105][105];
};

//输入优化【适用于正负整数】 
inline long long read() 
{ 
    long long X=0,w=0; 
    char ch=0; 
    while(!isdigit(ch)) 
    {
        w|=ch=='-';
        ch=getchar();
    } 
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); 
    return w?-X:X; 
}
// 重载*运算符 
Mat operator*(Mat A,Mat B)
{
    Mat temp;
    //memset(temp.mat,0,sizeof(temp.mat));// 将矩阵置0【零矩阵】 
    for(int i =0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ;j++)
        {
            temp.mat[i][j]=0;// 可以在这里做零矩阵，省一点时间
            for(int k = 0 ;k < n ;k++)
            {
                temp.mat[i][j] = (temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
            }
        }
    }
    return temp;// 返回矩阵A*B的结果 
}
// 重载^运算符 
Mat operator^(Mat A,long long k)//【坑点】这里的k一开始没有long long，导致全部WA 
{
    Mat base;
    // 将矩阵base置为单位矩阵【单位矩阵】 
    // 只需矩阵主对角线的元素为1即可，故可以只要一个循环
    for(int i=0;i<n;i++) base.mat[i][i]=1;

    // 矩阵快速幂【核心代码】 
    while(k)
    {
        if(k&1) base = base * A;
        A = A * A;
        k = k >> 1; 
    }
    return base;
}

int main()
{
    n=read();// 输入优化
    k=read();// 输入优化
    Mat ans;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            ans.mat[i][j]=read();// 输入优化
        }
    }
    ans=ans^k;// ans^k【矩阵快速幂】 
    // 输出矩阵
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%lld ",ans.mat[i][j]);
        }
        puts("");// 这里是换行，相当于printf("n");
    }
    return 0;
}

最后

以上就是大力大白为你收集整理的整数快速幂 & 快速幂取模快速幂快速幂取模矩阵快速幂例题的全部内容，希望文章能够帮你解决整数快速幂 & 快速幂取模快速幂快速幂取模矩阵快速幂例题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。