C++ – 快速幂

该怎样去加速幂运算的过程呢？既然我们觉得将幂运算分为n步进行太慢，那我们就要想办法减少步骤，把其中的某一部分合成一步来进行。

比如，如果 $n$ 能被 $2$ 整除，那我们可以先计算一半，得到 $a^\frac n 2$ 的值，再把这个值平方得出结果。这样做虽然有优化，但优化的程度很小，仍是线性的复杂度。

再比如，如果我们能找到 $2^k=n$ ，那我们就能把原来的运算优化成 $a^1,a^2,a^4,a^8...$ 只需要 $k$ 次运算就可以完成，效率大大提升。可惜的是，这种条件显然太苛刻了，适用范围很小。不过这给了我们一种思路，虽然我们很难找到 $2^k=n$ 但我们能够找到 $2^{k_1}+2^{k_2}+2^{k_3}+......+2^{k_m}=n$ 。这样，我们可以通过递推，在很短的时间内求出各个项的值。

我们都学习过进制与进制的转换，知道一个 $b$ 进制数的值可以表示为各个数位的值与权值之积的总和。比如， $2$ 进制数 $1001$ ，它的值可以表示为 $10$ 进制的 $1×2^3+0×2^2+0×2^1+1×2^0$ ，即 $9$ 。这完美地符合了上面的要求。 可以通过 $2$ 进制来把 $n$ 转化成 $2^{k_m}$ 的序列之和，而 $2$ 进制中第 $i$ 位（从右边开始计数，值为 $1$ 或是 ）则标记了对应的 $2^{i−1}$ 是否存在于序列之中。 譬如， $13$ 为二进制的 $1101$ ，他可以表示为 $2^3+2^2+2^0$ ，其中由于第二位为 ， $2^1$ 项被舍去。

如此一来，我们只需要计算 $a^1、a^2、a^4、a^8... a^{2^{k_m}}$ 的值（这个序列中的项不一定都存在，由 $n$ 的二进制决定）并把它们乘起来即可完成整个幂运算。借助位运算的操作，可以很方便地实现这一算法，其复杂度为 $\Omicron(\log n)$ 。

long long qpow(long long a, long long n, long long mod) {
    long long res = 1;
    a %= mod;
    while (n) {
        if (n & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res % mod;
}