信息奥赛｜快速幂

知识点概览 🚀

快速幂算法 是分治算法的典型应用之一。

合理运用 快速幂算法，可以使得幂运算的时间复杂度大大降低。

知识点详解 🎥

学习素材

编号	内容	链接	平台	创作者	推荐指数
1	快速幂算法介绍（CSDN）	链接1	CSDN	刘扬俊	🌟🌟🌟🌟🌟
2	快速幂讲解	链接2	B站	董晓算法	🌟🌟🌟🌟

代码模版

void fast_power(ll base, ll power) {
    ll res = 1;
    while (power > 0) {
        if (power & 1) {   //等同于 power % 2 == 1，但位运算速度更快
            res = ((res % M) * base % M) % M;
        }
        power >>= 1;  //等同于 power = power / 2，但位运算速度更快
        base = ((base % M) * (base % M)) % M;
    }
    cout << res % M << endl;
}

边界条件

接下来让我们考虑一下 快速幂算法的边界条件。

当幂指数 power==0 时，结果应该为 $1$。由于 res 的初始值就是 $1$，故结果正确。✅

当底数 base==0 时，结果应该为 $0$。此时循环中的 res * base 后，res 也会变为 0，结果正确。✅

🍉 PS：$0^n=0(n>0)$，$0^0$ 没有意义。

取模运算推导

不少快速幂算法的题目中，会使用这条数学性质：(a * b) % m = ((a % m) * (b % m))% m

这个性质也非常好证明：

假设 a = t1 * m + r1, b = t2 * m + r2

左边：(a * b) = (t1*t2 + r1*t2 + t1*r2) * m + r1*r2 → (a * b) % m = (r1 * r2) % m
右边：a % m =(t1 * m + r1) % m = r1 、 b % m =(t2 * m + r2) % m = r2 → (a % m) * (b % m) = r1 * r2 → ((a % m) * (b % m))% m = (r1 * r2) % m

故左边 = 右边，该性质成立。