1. 求解问题

求 a^k mod p问题，暴力方法需要 O(k)的时间复杂度，快速幂算法只要 O(logk)的时间复杂度

2. 核心思想

把 a^k转换成 a^(2^x1) * a^(2^x2) * a^(2^x3) * ... a^(2^xt)
等价与把 k拆分成若干个 2^xi相乘的形式，其实就是求k的二进制表示过程 k == 0b(101001)

tips

(a+b) mod p = ((a mod p) + (b mod p)) mod p
(a*b) mod p = ((a mod p) * (b mod p)) mod p

3. 代码模板

typedef long long LL;

int pmi(int a, int k, int p)
{
    LL res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = (LL)a * a;
    }

    return (int)res;
}