快速幂

所谓的快速幂，其目的是为了快速求幂，将时间复杂度从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;
}

最后

以上就是大力大白最近收集整理的关于整数快速幂 & 快速幂取模快速幂快速幂取模矩阵快速幂例题的全部内容，更多相关整数快速幂内容请搜索靠谱客的其他文章。