算法基础-快速幂 | 蓝桥杯

⭐简单说两句⭐

作者：后端小知识，CSDN后端领域新星创作者|阿里云专家博主

CSDN个人主页：后端小知识

🔎GZH：后端小知识

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

好的，亲爱的友友们，今天我们来讲解一个能提高幂运算效率的算法，他是什么呢？🧐没错，就是快速幂😎

概念

老规矩还是先看下概念

快速幂（Exponentiation by Squaring）是一种高效计算大整数乘方的算法，它利用了分治法的思想。这种方法的主要优势在于它减少了乘法运算的次数，从而提高了计算效率。

快速幂算法的时间复杂度为 O(log b)，其中 b 是指数。这使得它在处理大整数乘方时比传统的 O(b) 算法更高效。这种方法在计算机科学和密码学领域有广泛的应用，如模幂运算、大数乘法等。

思路

快速幂算法的基本步骤：

先学下概念：a^b，底数是a，指数是b

1. 如果指数为偶数，那么将底数平方，然后继续计算指数的一半。例如，计算 a^b 时，如果 b 是偶数，那么计算 (a*a)^(b/2)。
2. 如果指数为奇数，那么先计算 a^(b-1)，然后再乘以底数 a。例如，计算 a^b 时，如果 b 是奇数，那么就是计算 a*a^(b-1)。
3. 重复以上步骤，直到指数为1。此时，结果就是底数 a 的指数次幂。

我们举个实际的例子吧

计算：3^10

常规做法

答案 = 3x3x3x3… 10个三相乘，代码层面相当于循环10次，代码就不写了哈，很简单

快速幂做法

指数10为偶数：

3^10 = (3²⁾5 = 9^5

指数5为奇数

9^5 = 9×9^4

指数4为偶数

9×9^4 = 9x（9²⁾2

指数2为偶数

9x（9²⁾2 = 9x(81)^2 = 9x(81²⁾1

指数为1，结束运算

连起来就是

3^10 =9^5 = 9×9^4 = （9×81)^2 = 9x(81²⁾1

这样下来好像就运算了 4 次，是不是比前面算得快呢😎

代码实现

快速幂代码实现

#include<bits/stdc++.h>
using namespace std;
int a,n;
int quick(int a,int n){
	int ans = 1;
	while(n){
		//判断是不是奇数 
		if(n&1) ans *= a;
		a*=a;
		//相当于 n = n/2 
		n>>=1;
	}
	return ans;
}
int main(){
	int ans = quick(2,10);
	cout<<ans;
	return 0;
}

如果 数据量大的话，需要求余，就用同余做法

【ps】：中午时间不多，写得简洁，若有疑问，请留言，有空一定给解答

【都看到这了，点点赞点点关注呗，爱你们】😚😚

结语

谢谢你的阅读，由于作者水平有限，难免有不足之处，若读者发现问题，还请批评，在留言区留言或者私信告知，我一定会尽快修改的。若各位大佬有什么好的解法，或者有意义的解法都可以在评论区展示额，万分谢谢。
写作不易，望各位老板点点赞，加个关注!😘😘😘

💬

作者：后端小知识，CSDN后端领域新星创作者|阿里云专家博主

CSDN个人主页：后端小知识

🔎GZH：后端小知识

🎉欢迎关注🔎点赞👍收藏⭐️留言📝