模板 | 整数快速幂 & 快速幂取模

作者: 0与1的邂逅 | 来源:发表于2019-02-06 22:11 被阅读54次

模板 | 整数快速幂 & 快速幂取模
常用算法
几个数论小算法
快速幂取余
快速幂取模算法
快速幂取模算法
(矩阵)快速幂
快速幂
《算法竞赛进阶指南》0x01 位运算(笔记)
快速幂模板

快速幂：

所谓的快速幂，其目的是为了快速求幂，将时间复杂度从朴素算法的 $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("%d\n",pow(a,b));
}

接下来就是快速幂的表演时间了。

快速幂的原理：

还是原来的 $a^b$ ，我们会发现，其实指数b是可以拆成二进制的。通过式子 $a^{m+n} = {a^m*a^n}$ ，我们可以发现，一旦指数b拆成二进制，那么 $a^b$ 也可以进行相应的拆分。

例如，当b=11时，b的二进制为 $1011$ ，即 $11=1*{2^0}+1*{2^1}+1*{2^3}$ 。

那么， $a^{11}=a^{1*{2^0}+1*{2^1}+1*{2^3}}=a^{1*2^0}*a^{1*2^1}*a^{1*2^3}=a^1*a^2*a^8$ 。

经过上述操作，要求 $a^{11}$ ，我们只需要进行3次计算，而用朴素算法我们需要进行11次计算。

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

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

&运算：通常用于二进制取位操作，例如一个数x & 1 的结果就是取二进制的最末位的值。还可以判断这个数的奇偶性，如果x&1==0，则x为偶数；如果x&1==1，则x为奇数。
>>运算：在这里是作为除法来使用，例如一个数x，x >> 1就表示x右移一位，即x=x/2。

具体代码：【快速幂】【模板】

//【快速幂】 
#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("结果：%d\n",pow(a,b));
}

其中，主要要理解base*=base这一步：
因为 $base*base==base^2$ ，下一步再乘，就是 $base^2*base^2==base^4$ ，然后同理

$base^4*base^4==base^8$ ，由此可以到

$base-->base^2-->base^4-->base^8-->base^16-->base^32.......$

指数正是 $2^i$ ，再看上面的例子， $a^{11} = a^1*a^2*a^8$ ，这三项就可以完美解决了，快速幂就是这样。

快速幂取模：

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

下面我们以 $a^bmod 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}modc$ $=$ $(a mod c)^b$ $mod c$

方法二：

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;
}