174.快速幂题解

写在前面的话：十年oi一场空，不开long long见祖宗

1、求幂运算：

（你肯定会说，这道题不是简简单单吗？） 那么我们来看看常规的思路是怎么解决的

#include <iostream> 
#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 = (a*a)^8   注意取余
	if(n%2 == 0) return ksm(a*a%m, n/2, m);
	// 如果n为奇数: a^15 = a*(a^14)  注意取余
	else return a*ksm(a, n-1, m)%m;
}

循环实现：

这种方法相比递归要难以理解一点

#include <iostream> 
#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 = res*a%m;
		// 不管n是奇数还是偶数，直接指数砍半
		//（n是偶数的话不影响，n是奇数上面已经处理了）
		n /=2;
		// 底数也要改变： 2^14 = (4)^7
		a = a*a%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、总结

以上代码不要直接使用，要自行调试

看懂的同学可以在评论区留言哦

公式太多，难免出错，欢迎指正^_^