快速幂

作者: 风之旅人c | 来源:发表于2020-03-04 10:45 被阅读0次

(矩阵)快速幂
快速幂
快速幂,矩阵快速幂
模板 | 整数快速幂 & 快速幂取模
常用算法
2018-07-09-快速幂
快速幂
快速幂
快速幂
快速幂

快速幂

如果要我们求解 $a^b$ ，正常的做法往往是 $O(n)$ 的算法，当数字很大的时候会耗费较多的时间，现在我们采用快速幂，可以将时间复杂度降低到 $O(log_2(n))$ 。

模板题目

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

题目简介

给定三个正整数 $b,p,k$ ，求解 $b^pmodk$ 。

快速幂讲解

$a^xa^y = a^{x+y}$
如果我们将 $a$ 自乘，会得到 $a^2$ ，接着自乘，会得到 $a^4$ ，以此类推下去。

如果我们要求解 $a^b$ ，假设 $b=11$ ， $b = (11)_{10} = (1011)_{2}$ ，从左至右分别为 $8,2,1$ ，这样 $a^{11} = a^8*a^2*a^1$ 。

因此，快速幂求解 $a^{11}$ 的过程如下：

取base = a，代表 $a^1$ ；取ans=1，用来存储结果；b=11，二进制下位1011。
b的最后一位是1，则ans *= base，代表 $a^{11} = a^8*a^2*a^1$ 中的 $*a^1$ 。
base自乘，现在base = $a^2$ ，同时b右移一位，b= $101_{(2)}$ ，这时候b的最后一位还是1，则ans *= base，代表 $a^{11} = a^8*a^2*a^1$ 中的 $*a^2$ 。
base自乘，现在base = $a^4$ ，同时b右移一位，b= $10_{(2)}$ ，这时候b的最后一位是0，则ans不变。
base自乘，现在base = $a^8$ ，同时b右移一位，b= $1_{(2)}$ ，这时候b的最后一位还是1，则ans *= base，代表 $a^{11} = a^8*a^2*a^1$ 中的 $*a^8$ 。

int quickPower(int a, int b)//是求a的b次方
{
    int ans = 1, base = a;//ans为答案，base为a^(2^n)
    while(b > 0)//b是一个变化的二进制数，如果还没有用完
    {
        if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
            ans *= base;//把ans乘上对应的a^(2^n)

        base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
        b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
    }
    return ans;
}

当然，我在洛谷上也看到了另外一种快速幂的理解方法。
下图是2017年NOIP普及组的完善程序第1题：

NOIP普及组

从头开始。若当前 ppp 为偶数，咱们不着急，只需把 xxx 自乘，然后 $p /= 2$ （即考虑下一层，下几层会帮我们乘上 $(x^2)^{p/2}$ 的）。

若当前 $p$ 为奇数，说明 $x^p = x*(x^2)^{(p-1)/2}$ 中前面那个 $x$ 的存在， $ans *= x$ 。然后继续考虑下一层（下几层会帮我们乘上 $(x^2)^{(p-1)/2}$ 的）。注意，这里的 xxx 不是指题目开始给出的 xxx，而是当前层的 xxx 应有的值，这跟上面的 $base$ 是一样的。

取余运算

快速幂经常结合取余运算：

$(A+B) mod b=(A mod b+B mod b) mod b$
$(A×B) mod b=((A mod b)×(B mod b)) mod b$

while(b > 0)
    {
        if(b & 1)
        {
            ans *= base;
            ans %= m;
        }

        base *= base;
        base %= m;
        b >>= 1;
    }

解题代码

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

long long a, b, m;

long long quickPower(long long a, long long b)
{
    long long ans = 1, base = a;
    while(b>0)
    {
        if(b&1)
        {
            ans *= base;
            ans = ans % m;
        }
        base *= base;
        base %= m;
        b >>= 1; 
    }
    return ans;
 } 

int main()
{
    cin >> a >> b >> m;
    cout<<a<<"^"<<b<<" mod "<<m<<"=";
    cout<<quickPower(a,b)%m;
    return 0;
}