快速幂（qmi）

本期同步视频，建议边看视频遍看分享~

B站同步视频

所谓快速幂，就是快速的求出a ^ k % p的结果。

那到底如何去求呢

快速幂的核心思路就是反复平方法。——yxc老师。

那何谓反复平方法？
其实就是预处理出来这些数：

(a ^ (2 ^ 0)) % p
(a ^ (2 ^ 1)) % p
(a ^ (2 ^ 2)) % p
……

然后想方设法把这些数拼成a ^ k % p。
好大家想一下如何去拼。

**

想完的同学请继续。
我们可以先把k转化为2进制。
然后如果k的二进制表示的第i为是1，就res = res * qmi[i] % p;（但实际要比这个简单多了。）
然后k右移1位。
最后返回res。

然后我们举个例子吧。

比如2 ^ 5 % 5

首先预处理出来所有平方。

qmi[0] = (2 ^ (2 ^ 0)) % 5 = 2
qmi[1] = (2 ^ (2 ^ 1)) % 5 = 4 也等于 qmi[0] ^ 2
qmi[2] = (2 ^ (2 ^ 2)) % 5 = 1 也等于 qmi[1] ^ 2

接下来我们算出5的二进制表示。

5的二进制表示 = (101)

最后组合出res

  2 ^ 5 % 5
= 2 ^ (101) % 5
= (qmi[0] * qmi[2]) % 5
= (2 * 1) % 5
= 2

见证奇迹的时刻

2 ^ 5 = 32
32 % 5 = 2
!!!

接下来大家看下模板：

ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = (ll) res * a % p;
        k = k >> 1;//k >>= 1;
        a = (ll) a * a % p;
    }
    return res;
}

我们可以把a进行反复平方从而不需要qmi数组。

然后是一道题：快速幂

直接应用模板即可。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, a, k, p;
ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = (ll) res * a % p;
        k = k >> 1;//k >>= 1;
        a = (ll) a * a % p;
    }
    return res;
}
int main()
{
    cin >> n;
    while(n --)
    {
        cin >> a >> k >> p;
        cout << qmi(a, k, p) << endl;
    }
    return 0;
}

留道作业：请利用快速幂的思想分析乘法。

64位整数乘法

选自《算法竞赛进阶指南》。

作业下期讲解。

今天的分享就到这里了，下期见。

未经允许，请勿抄袭！

这是我的全部分享

bye~