$\Huge\color{orchid}{点击此处获取更多干货}$

整数型快速幂

幂运算其实在C语言标准库里就已经有了，其函数原型为double pow(double x, double y)，用来计算浮点数的幂$x^y$，而根据众多原因（以下省略）可知，浮点数的运算比整数要慢一些。对于正整数型的$x^y$，可以有更快的计算方法

首先，所有的整数类型在计算机中都用二进制来表示，因此每个正整数又可以有另一种得出的方法：$\sum_{i=0}^{M-1}(b_i*2^i)$，其中$b_i$是该整数二进制的各数位，$M$是存储该整数用到的最大二进制位数（8，16，32，64比较常见）。考虑到幂运算的特点，当底数$x$和指数$y$都是正整数时，如果$y$用上面的方式来表示，那么就有下面这个公式：
$$x^y=x^{{\textstyle \sum_{i=0}^{M-1}(b_i*2^i)}}={\textstyle \prod_{i=0}^{M-1}(x^{b_i*2^i})}={\textstyle \prod_{i=0}^{M-1}(x^{2^i})^{b_i}}$$

据此，正整数的快速幂流程也很清楚了：
0. 初始化，结果位1
1. 枚举指数二进制的每一位，从最低的$i=0$开始
2. 如果该位是1，则在结果中乘上$x$的$2^i$次方
3. 如果该位是0，由于正整数0次幂永远是1，结果保持不动

实际存储时，$M$位二进制数位中，最高的几位会是连续的0，它们可以不必累乘进结果中，因此如果当前位表示的$2^i$已经比$y$大，可以直接停止。对于$x$的$2^i$，由于每一轮相比上一轮是平方的关系，因此可以预先保存底数$x$，每次枚举累乘完成之后，就可以将其自乘。另外，整数分为有符号和无符号，有符号整数会根据最高的符号位是1还是0判断当前数值是负数还是正数，而无符号数将每一位都当作数值位，数值默认是正数。考虑到后期数值可能会很大，这里选择C语言时代就存在的无符号64位整数类型$\text{size_t}$

C++ 代码

/**
 * @brief 正整数专用快速幂
 * @param base 底数x
 * @param power 指数y
 * @param mod 模数（每次乘法后取模）
 * @return 取模后x^y的值
 */
size_t quickPower(size_t base, size_t power, size_t mod) {
    size_t ans = 1;
    while (power > 0) {                 //枚举二进制每一位
        if (power & 1) {                //是1就乘上对应的2幂次，是0就不动
            ans = (ans * base) % mod;
        }
        base = (base * base) % mod;     
        power >>= 1;                    //右移可以将高位移到低位便于判断，高位会自动补0
    }
    return ans;
}