快速幂模板

缘起

快速幂是最基本的二分思想, 作为程序员必须要熟知.

分析

1
求 3^2000 除以7 的余数

其实就是

3^2000=(3^(1000))^2, 所以我们只需要知道 3^1000模掉7的余数，然后平方即可. 而3^1000=(3^500)^2, 所以只需要知道3^500模掉7的余数.

更一般的，如果我们想知道B^a 模掉P的余数，则将a展成二进制

例如12 = 2^3+2^2, 则 B^12, 可以先计算B^2模掉P的余数，则得到之后将B替换为该余数，不妨仍记为B，则需要知道的是B^6模掉P的余数，同理，可以计算B^2模掉P的余数，仍记为B，则只需要计算B^3模掉P的余数，此时3是奇数，则若记最终的答案是ans（初始值为1），则让ans=B*ans模掉P的余数，则一个B就挪出去了，剩下B^(3-1)=B^2, 则只需要计算B^2模掉P的余数，则只需要计算B^2模掉P的余数，仍记为B，则只需要计算B模掉P的余数，1是奇数，所以挪一个进ans，即计算ans=ans*B, 则剩下B^0模掉P的余数计算，此时退出循环. 综上，整个计算过程如下，也就是快速幂的板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef long long LL;
LL qsm(LL B, LL a, LL P) // 计算 B^a 模掉P的余数
{
    LL ans = 1;
    while(a)
    {
        if(a&1) // 如果a是奇数
        {
            ans = ans * B % P;           
        }
        if(a > 1) // 例如a是1的话，就不会进行下面的计算
        {
            B = B * B % P;
        }
        a = a >> 1;
    }
    return ans;
}