1、求幂运算： 首先我们来看一道经典求幂的问题：假设给你三个整数 、 、 ，现在你需要求出的值，你会怎么做呢？
（你肯定会说，这道题不是简简单单吗？） 那么我们来看看常规的思路是怎么解决的
#include #define ll long long using namespace std;
int main() { int a,n,m; ll res = 1; cin>>a>>n>>m; for(int i=1;i<=n;i++){ res = res*a%m; } cout<<res; return 0; } 在上面的代码中，我们只用了一个for循环就解决了问题，那么时间复杂度就是，能过的数据范围就是
现在我们稍微把题目升级一下，给上面的题目加上范围：
升级之后，如果你还想用上面的方法去提交，恭喜你喜提TLE
也就是说复杂度的算法不能通过的数据范围，有没有好的优化方法呢？
接下来就有请我们的快速幂登场啦。
2、快速幂原理： 在上面，我们已经讨论过数据范围较小的求幂运算了，下面我们就来优化一下求幂的运算(需要一定的初中数学知识)
完整题目如下：
假设给你三个整数 、 、 ，现在你需要求出的值，其中：
我们先从数学的角度来看一下优化的原理
在数学上，幂运算的公式变化如下：
熟练之后： 为 正 整 数
其他用法：
我们用两个例子来看一下快速幂过程：
例1：求 在数学上，我们可以优化计算:
根据以上的计算过程，我们只需要计算5次就能得到结果，相比之前的16次循环，已经达到了优化的效果。
相信聪明的同学到这里就已经能看出我们优化的过程和二分有点像，不过还有一部分的同学肯定也想问，如果指数是奇数要怎么处理呢？
例2：求 (奇数项 底数：3)
(奇数项 底数：9)
(奇数项 底数：91)
最后乘上之前的每一个奇数项底数：
通过以上两个例子，我们可以看到优化后的计算量依然远远小于第一种方法
以上就是快速幂的计算过程，那么它的时间复杂度是多少呢？如果让你求最少需要计算多少次呢？
快速幂时间复杂度，原理和二分很类似
原理我们就讲到这里，接下来我们进入代码部分，下面给大家介绍两种方法：
3、代码 递归实现： 注意开long long！！！注意取余！！！
// 先定义递归函数：ksm(a,n,m)表示求a的n次方，并对m取模 ll ksm(ll a, ll n, ll m){ // 递归边界，当n等于1的时候就直接得出结果: a^1 = a if(n == 1) return a%m; // 如果n为偶数: a^16 = (aa)^8 注意取余 if(n%2 == 0) return ksm(aa%m, n/2, m); // 如果n为奇数: a^15 = a*(a^14) 注意取余 else return a*ksm(a, n-1, m)%m; } 循环实现： 这种方法相比递归要难以理解一点 #include #define ll long long using namespace std;
int main() { ll a,n,m; ll res = 1; // 存放结果 cin>>a>>n>>m; while(n){ // 如果是奇数，就把当前的a乘的结果里面 // 例：res = 2^15 变成 res = 2 * (2^14) if(n%2 == 1) res = resa%m; // 不管n是奇数还是偶数，直接指数砍半 //（n是偶数的话不影响，n是奇数上面已经处理了） n /=2; // 底数也要改变： 2^14 = (4)^7 a = aa%m; } cout<<res; } 4、关于本题： 读完题不难发现这是一道等比数列求和的问题，项数比较多，用公式法不能得出准确的结果，暴力又要超时
写了这么多，好像这道题并没有完全解决。我们目前只解决了快速幂的部分，还有等比数列求和的部分呢，要怎么解决？
关于等比数列求和，我们也可以使用二分的方法来优化。后面只给大家提供思路，剩下的自己去想
例：当a=3，b=10，其实就是求首项和公比都为3的等比数列前10项和，我们可以写下一下的过程：
采用二分的优化方法， 把上式子拆分成两部分(如下面两个小括号的部分)：
我们对后面的部分提取一个公因子，那么原式就可以变成下面这样
提取公因式：
如果当项数为奇数呢？我们对继续运算
当项数为奇数时，我们用之前的快速幂直接计算最后一项，在加上前面偶数项的结果即可
继续对前面的偶数项进行二分，并对后面的几项提取公因子
......(一直递归到n=1的时候结束) 参考代码：
// 表示公比为a的等比数列前n项和 ll fun(ll n, ll a) { if (n == 1) return a; // 当n是奇数(位运算判断)，有奇数项求和：分成前(n-1)个偶数项，和第n项 if (n & 1) return (fun(n - 1, a) + ksm(a, n)) % 1234567; // 当n是偶数，直接二分 else return fun(n / 2, a) * (ksm(a, n / 2) + 1) % 1234567; } 5、总结 以上代码不要直接使用，要自行调试
看懂的同学可以在评论区留言哦
公式太多，难免出错，欢迎指正^_^