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

比眉伴天荒 2024-04-20 07:36 72阅读 0赞

⭐**简单说两句**⭐

> **作者：****后端小知识**，**CSDN后端领域新星创作者|阿里云专家博主**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

![在这里插入图片描述][492a57c3af714760922348dce1afcd6a.png]

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

### 概念 ###

老规矩还是先看下概念

快速幂（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 = (32)5 = 9^5

指数5为奇数

9^5 = 9x9^4

指数4为偶数

9x9^4 = 9x（92)2

指数2为偶数

9x（92)2 = 9x(81)^2 = 9x(812)1

指数为1，结束运算

连起来就是

3^10 =9^5 = 9x9^4 = （9x81)^2 = 9x(812)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】：中午时间不多，写得简洁，若有疑问，请留言，有空一定给解答

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

![抽象工厂  引导关注][199c21e10d589f1889bfb9e864daecc6.png]

**结语**

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

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

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[492a57c3af714760922348dce1afcd6a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/159c8808d21e40beb365368d19e65930.png
[199c21e10d589f1889bfb9e864daecc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/26b5c0cc31b7461d8730a5176f201083.png