今天带来的是P1226 【模板】快速幂。这道题说是一道题，但其实就是个模板。属于你不知道的时候，苦思冥想怎么也想不出来，知道后感觉非常神奇。先贴一下代码。

#include <iostream>
using namespace std;

long long fastPow(long long a, long long b, long long p) {
    long long res = 1 % p;
    while (b > 0) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    long long s = fastPow(a, b, p);
    cout << a << "^" << b << " mod " << p << "=" << s << endl;
    return 0;
}

快速幂其中首先是利用到了分治的思想。分治，即分而治之，将大问题分解为小问题，分别求解，最后合并结果。从题目给到的数据范围都到2的31次方了，可见如果用暴力的方法算，是肯定会超时的。我也写了暴力的代码去提交了一下，果然超时了。那么此时有没有别的方法呢，正如题目所说，那就是快速幂。

设一个数a自乘b次叫做a^b

那么：a ^b * a ^c = a ^{b + c}

而 a ² = a * a , a ⁴ = a ² * a ² , a ⁸ = a ⁴ * a ⁴ ……

由此，就可以快速得到a的指数为2的n次方的幂。但如果指数不是2的n次方呢？我们知道计算机里的数字都可以用二进制来表达，比如105就可以用1101001来表示，也就是1+8+32+64。那么就可以分解为这几个来乘算，另外计算机还有几种特殊的计算，&，叫按位与，就是把按照二进制的位数对每一位进行与运算，如果对1进行与运算的话，也就能判断是不是偶数；和>>，叫右移，比如105右移后就变成110100。通过这些就可以方便的进行计算，来进行指数的判断和幂的计算。

如果没有看懂，可以看一下这个视频。https://www.bilibili.com/video/BV16Z4y1M7y1/?vd_source=ea8222e2711cd9aa0250c479e4e3a4f0