2024 - 11 - 26 - 第 33 篇 - 算法笔记
C++、快速幂算法
作者(Author): 郑龙浩 / 仟濹(CSDN账号名)

快速幂算法

一、为什么接触这个算法

在做 洛谷P1045 这个算法题的时候，我发现用 普通的高精度算法，依然无法解决大数计算使用内存太大 的问题，然后紧接着接触了压位高精度算法，发现依然还是不能完全解决(也或许我是用压位高精度算法写的该问题代码存在bug吧)。

然后我看题解的时候，发现有大佬使用高精度快速幂解决了该问题，然后我就去学习了一下**【快速幂算法】，然后再将高精度算法和快速幂算法**结合去做该题。

二、大体思路

b站某up主的视频，看了之后就悟了

https://www.bilibili.com/video/BV16Z4y1M7y1/?share_source=copy_web&vd_source=123565abb60ee9d849adaeb118d98b85

不知道如何清晰的将思路写出来，看了该up主的视频以后，通过该up主的动画我才明白，语言解释太啰嗦了，感觉不如看动画演示来的易懂。

一个很重要的地方就是，要将 10 进制的数字 看做 2 进制去思考，会发现一个很重要的规律

三、代码实现

写了两种方法，思路是相同的，只不过一个是模除运算，一个是位运算

#include <iostream>
using namespace std;// 快速幂算法计算 a^n// 方法1
long long newpow1( long long num, long long n ){long long ans = 1;while( n ){if( ( n & 1 ) == 1 ) ans *= num;num *= num;n >>= 1;}return ans;
}// 快速幂算法计算 a^n// 方法2
long long newpow2( long long num, long long n ){long long ans = 1;while( n ){if( n % 2 == 1 ) ans *= num;num *= num;n /= 2;}return ans;
}int main( void ){cout << newpow1( 2, 22 ) << endl;cout << newpow2( 2, 22 ) << endl;return 0;
}