快速幂

快速幂主要解决形如

a^k \quad mod \quad p

的问题

一个非常简单的做法便是用一个k次的循环，每一次将ans累乘一个a再对p取模，这样的朴素算法时间复杂度是O(k)

现在要介绍的快速幂算法可以在O(\log_{}{k} )的复杂度来解决这个问题

快速幂的核心思想是：

1. 对于问题a^k \quad mod \quad p，首先处理出

   a^{2^i},i \in [0,\log_{}{k}]

2. 将k分解成二进制形式

   (k_i)_2

3. 此时

   ans=a^k \quad mod \quad p =\prod_{j}^{} m_j \quad mod \quad p \\
   j是k的二进制写法中1的位置

也就是说，我们将a^k中的k写成了二进制的形式，用十进制与二进制的转换关系来表示这个答案，而使用的数字a^{2^i}可以通过自乘获得之

下面用一个例子来辅助理解上面的过程 对于问题

4^3 \quad mod \quad 9

分解二进制的结果是

3=(11)_2

也就是说

4^3 = 4^{2^0} \times  4^{2^1}

而

4^{2^0}=4 \\
4^{2^1}=4 \times 4 =4^2\\
(如果需要)4^{2^2}=4^{2^2}

所以

4^3 \quad mod \quad 9 = 1

上代码

ll qmi(ll a,ll k,ll p){//a ^ k % p
    ll res=1;
    while(k){//while(k)k>>1;是将k分解为二进制数的标准做法
        if(k & 1)   res *= (ll)a % p,res %= p; //如果k的二进制末尾是1则累乘
        a *= (ll)a % p,a %= p; //a自累乘
        k >>= 1;
    }
    return res % p;
}