AcWing 875. 快速幂

一、什么是快速幂

答：快速求出 \(a^k \ mod\ p\) 的结果！

二、快速幂的原理

答：快速幂算法的原理是通过将指数拆分成几个因数相乘的形式，来简化幂运算。在我们计算\(3^{13}\) 的时候，普通的幂运算算法需要计算\(13\)次，但是如果我们将它拆分成\(3^{8+4+1}\) ，再进一步拆分成 只需要计算\(4\)次。嗯？哪来的\(4\)次？，别急，接着看。

这种拆分思想其实就是借鉴了二进制与十进制转换的算法思想，我们知道\(13\)的二进制是\(1101\)，可以知道：
\(13=1×2^3 + 1×2^2 + 0×2^1 + 1×2^0 = 8 + 4 + 1\)

原理就是利用位运算里的位移“>>”和按位与“&”运算，代码中\(k\&1\)其实就是取\(k\)二进制的最低位，用来判断最低位是\(0\)还是\(1\)，再根据是\(0\)还是\(1\)决定乘不乘，不理解的话联系一下二进制转换的过程。
\(k >>= 1\)其实就是将k的二进制向右移动一位，就这样位移、取最低位、位移、取最低位，这样循环计算，直到指数\(k\)为\(0\)为止，整个过程和我们手动将二进制转换成十进制是非常相似的。

普通幂算法是需要循环指数次，也就是指数是多少就要循环计算多少次，而快速幂因为利用了位移运算，只需要算“指数二进制位的位数”次，对于\(13\)来说，二进制是\(1101\)，有\(4\)位，就只需要计算\(4\)次，快速幂算法时间复杂度是\(O(logn)\)级别，对于普通幂需要计算一百万次的来说，快速幂只需要计算\(6\)次，这是速度上质的飞跃，但是需要多注意溢出的问题。

三、举个栗子

把\(3^{13}\)进行转化：
\(3^{13}=3^{8+4+1}=3^8×3^4×3^1\)
如果我们能求出\(3^1\),\(3^4\),\(3^8\)，我们就可以求出最后的\(3^{13}\)，因为把它们乘在一起就可以了嘛。那怎么求呢？

\(3^1\)可以求，因为就是\(3\)嘛，其它的呢？其它的有哪些需要我们提前准备好呢？
有： \(3^1\)，\(3^2\)，\(3^4\)，\(3^8\) ，有上面的这几个，就可以完美的组装出\(13\)了！

四、简单粗暴快速幂（无用版本）

此方法是我用来方便理解的，不可用于实际工作中，或者说，没有实用价值。因为一来系统中有现成的\(pow(n,m)\),另一个是不防溢出基本在数论题中无用。

#include 
using namespace std;

typedef long long LL;

int qmi(int a, int k) {
    int res = 1; 
    while (k) {                    
        if (k & 1) res = res * a;  
        k >>= 1;                   
        a = (LL) a * a;                 
    }
    return res;
}


int main() {
    cout<

#include 
using namespace std;
typedef long long LL;

int n;

// 快速幂 (a^k)%p
int qmi(int a, int k, int p) {
    int res = 1;                            //答案
    while (k) {                             //一路让k变小直到为0停止
        if (k & 1) res = (LL) res * a % p;  //如果k的个位是1的话
        k >>= 1;                            //右移一位
        a = (LL) a * a % p;                 //1-2-4-8-16，就是每进一位，是把a=a*a,注意使用long long 防止在乘积过程中爆了int
    }
    return res;
}

//快速幂
int main() {
    scanf("%d", &n);
    while (n--) {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}