快速幂详解

快速幂这个东西比较好理解，但实现起来总会忘记一些细节，今天把它总结一下防止忘记。

---

题目：

原题链接：点击此处

a^b

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p ,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

$ 1\leq a,b,p\leq 10^9 $

输入样例：

1

3 2 7

输出样例：

1

2

---

原理：

快速幂的目的就是为了做到快速求幂，假设在不使用快速幂的情况下解这道题，那么就是把 a 连续乘 b 次，这样的时间复杂度是 $O(b)$ 也就是 $O(n)$ 级别的。虽然这样看起来也很快了，但是题目的数据范围最大为 $1e9$ ，这样子的速度完全是不够的。但是使用快速幂的算法解决的话，他的复杂度将会下降到 $O(logn)$，如果 n 很大，速度差就是天壤之别了。快速幂的原理如下：

假设我们求 $a^{11}$ ，那么 11 是可以拆分成二进制形式 1011 ，该数字的二进制的第 i 位的权值为 $2^{i-1}$，所以 $a^{11}=a^{2^0+2^1+2^3}$。我们可以将他再转化一下变成 a^{2^0}*a^{2^1}*a^{2^3}=a^1*a^2*a^8。可以看出通过这样的转化，原本需要乘 11 次的运算可以减少到 3 次。但是要怎么操作才能转化成这三项呢，下面给出详细解释。

由于上面的式子是在二进制数的基础上转化来的，我们很容易就能想到用 位运算 会简化我们的操作。这里我们来介绍一下位运算中的 & 和 >> 。
&运算的运算规则是0&0 = 0; 0&1 = 0; 1&0 = 0; 1&1 = 1;即有0则为0，他通常用于二进制的取位操作，例如一个数 x & 1 就是取二进制的末位，因为 1 的二进制表示为 00000001，假设 x 的二进制表示为 10010001，那么他们二进制的每一位都将按照运算规则运算，由于1的二进制表示除了末位其他都为0，那么 x & 1 的值除了末位其他位也都是0，由于x的末位是1，所以答案为00000001则为1。
>>运算就是将二进制去掉最后一位，高位补零，例如8 >> 1。8的二进制表示为1000，去掉最低位，高位补零后为0100，所以答案是4。由于>>运算比较简单，这里不再多说。

知道如何通过二进制转化式子后，我们就可以写出快速幂的模板。先不多说，上了代码再解释。

int qmi(int a, int b, int p)
{
    int ans = 1, t = a;
    while (b) {
        if (b & 1) res = res * 1ll * t % p;
        t = t * 1ll * t % p;
        b >>= 1;
    }
    return ans;
}

这里要注意，题目只要求取模后的值，所以最终答案要取模。而这里每一步都取模的原理是 (a * b) % p = (a % p * b % p) % p，这么做是为了防止数据太大而溢出。ans * 1ll也是为了防止溢出。1ll是long long类型，所以会暂时以long long的类型来运算。
代码很短，如果记不住原理的，死记也可以，这里还可以将快速幂写成自定义函数，方便重复使用。
所以这道题使用上面那套模板就能轻松AC。

#include<iostream>
using namespace std;
int qmi(int a, int b, int p)
{
    int ans = 1, t = a;
    while (b) {
        if (b & 1) ans = ans * 1ll * t % p;
        t = t * 1ll * t % p;
        b >>= 1;
    }
    return ans % p;
}
int main(){
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
    return 0;
}

---

练习

下面给出另外一道题目，与上一题的做法类似，大家检测一下自己是否学会了快速幂的使用。

原题链接：点击此处

64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式

第一行输入整数a，第二行输入整数b，第三行输入整数p。

输出格式

输出一个整数，表示a*b mod p的值。

数据范围

$1\leq a,b,p\leq 10^{18}$

输入样例：

3
4
5

输出样例：

2

解法：

#include <iostream>
using namespace std;
int main()
{
    unsigned long long a, b, p;
    cin >> a >> b >> p;
    unsigned long long ans = 0;
    while (b) {
        if (b & 1)
            ans = ans + a % p;
        a = a * 1ll * 2 % p;
        b >>= 1;
    }
    cout << ans % p << endl;
    return 0;
}

---