快速幂

幂还有快速？

我们首先来思考一个问题，对于 $7^6$ 如何求。

作为一个人类，你的求法一定是先算出 $7\times7=49$，然后接着算出 $49\times7=343$，…… ，$16807\times7=117649$。因为人类并不适合算两位数以上的乘法(一位数还勉强可以瞪眼)，所以有些时候我们的思维便会限制在这个里面。

但是，我们了解，对于计算机CPU来说 $7\times7$ 和 $1561564\times1561564$ 几乎没啥差别(毕竟慢的是存储)，因此我们可以加快幂运算。

又是二进制

没错，你没看错，又是二进制！

我们早就知道了，对于任意一个二进制数，我们可以拆分成多个 $2^n$ 相加的形式。如：$6_{10}=(110)_2=(100)_2+(10)_2=2^2+2^1$。

相应的，任意一个数 $x$ 的 $k$ 次方 $x^k$ 都可以拆分成多个 $x^{2^n}$ 相乘的形式。这时候，我们发现，原本的 $O(k)$ 次操作被优化到了 $O(\log{k})$。而我们只需要将 $x^{2^n}$ 不断的自己乘自己，就可以得到所有我们需要的数。

例子：计算 $7^{14}=7^2\times7^4\times7^8$

代码

[P1226 【模板】快速幂&取余运算][https://www.luogu.com.cn/problem/P1226]

//只需要注意mi函数即可
#include <cstdio>
int a, b, p;
inline int mi(int n, int m, int mod, long long sum = 1, long long ans = 1)
//n表示底数,m表示指数,mod为模数,sum为累加器,ans为结果
{
    sum = n;  //初始化累加器至n^1
    while (m) //保证指数不为0
    {
        if (m & 1) //如果最后一位是1,则应该乘上
        {
            ans *= sum;
            ans %= mod;
        }
        sum *= sum; //累加器自乘
        sum %= mod;
        m >>= 1; //这一位已经处理完毕,开始处理下一位
    }
    return ans % mod;
}
int main()
{
    scanf("%d%d%d", &a, &b, &p);
    printf("%d^%d mod %d=%d\n", a, b, p, mi(a, b, p)); //奇奇怪怪的输出方式
}

链接

其他更快的方法，参见[]、[]。