零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第十五天了。
  随着时间的推移，坚持下来的人越来越少，这正是绝地反击的最好时机，坚持到最后的人，往往可以力挽狂澜。在刷题的过程中，总结自己遇到的坑点，写出 「 解题报告 」 供他人学习，也是一种自我学习的方式。这就是经典的帮助他人的同时，成就自己。目前， 「 万人千题 」 社区 每天都会有五六篇高质量的 「 解题报告 」 被我 「 加精 」。如果觉得自己有能力的，也可以来发布你的 「 解题报告 」。千万级流量，你我共同拥有。

一、概念定义

  二分快速幂的概念很简单，思想很经典，是个经典的 分而治之 问题。对于常量表达式：$$a^{b}modc$$ 我们可以将它分三种情况求解：$$a^{b}modc=\{\begin{array}{ll}1modc& b为0\\ a(a^{(b-1)/2}{)}^{2}modc& b为奇数\\ (a^{b/2}{)}^{2}modc& b为正偶数\end{array}$$
  除了 $b=0$ 的情况立马可以得到解，$b$为奇数或者正偶数时，都可以将 $b$ 的范围缩小一半。所以，可以将时间复杂度从原本的 $O(b)$ 变成 $O(lo{g}_{2}b)$。

二、题目描述

  已知三个正整数$a,b,c(a,b\le 10^{18},c\le 10^9)$，求：$f(a,b,c)=a^{b}modc$

三、算法详解

  利用程序的递归思想，可以把函数描述成如下的形式：
$$f(a,b,c)=\{\begin{array}{ll}1modc& b为0\\ af(a,\frac{b-1}{2},c{)}^{2}modc& b为奇数\\ f(a,\frac{b}{2},c{)}^{2}modc& b为正偶数\end{array}$$

四、源码剖析

#define ll long long
ll f(ll a, ll b, ll c) {if (b == 0)return 1 % c;           // (1)ll v = f(a*a % c, b/2, c);  // (2)if (b % 2)v = v * a % c;          // (3)return v;
}

• $(1)$ 考虑 $b=0$ 的情况；
• $(2)$ 考虑 $b$ 为非零偶数的情况；
• $(3)$ 考虑 $b$ 为奇数的情况；

五、推荐专栏

  本文介绍的二分快速幂的内容较为基础，除了用递归求解，还可以用二进制的方式，请同学自行思考。更多进阶内容，敬请关注：

💜《夜深人静写算法》💜   （三十）二分快速幂

六、习题练习

序号	题目链接	难度
1	Pow(x, n)	★☆☆☆☆
2	超级次方	★★☆☆☆
3	(困难) 好因子的最大数目	★★★★☆

👇🏻 关注公众号 观看 精彩学习视频👇🏻