一、概念：
快速幂是一种高效的指数运算方法，通过指数折半或二进制位运算减少计算次数。它的核心思想是利用二进制表示法或指数折半来加速计算，从而避免大量的循环操作。
二、学习路径：
- 了解基本概念
- 掌握暴力解法、快速幂（二进制）、快速幂（指数折半）
- 快速幂于库函数<cmath>中pow()的区别。
- 进行如下题目练习，以达到掌握目的：
- 数的次幂（基础）-> 小数第n位（进阶）-> 堆的计数（综合）-> 乘法逆元（拓展）
三、用法：
快速幂可有多种方法实现，最主要的两种是，二进制、指数折半方法实现。
1、BF暴力解法：
谈到算法的起源与优化，首先就要想到他们的原身-暴力解法，这是根，亦是魅力。
#include "bits/stdc++.h" using namespace std; #define ll long long ll Pow(int base, int exponent){ int result = 1; for(int i = 0; i<exponent; ++i){ result*=base; } return result; } int main(){ // 如何求快速幂，对指数进行取余， ll num = Pow(2,4); cout<<num<<endl; return 0; }
一招遍历走天下。
但是如果是1万次方，真的要循环1万次吗？虽然可行，但极度浪费运算时间。
于是提出了二进制法，将指数转化为二进制，通过位运算进行计算-大神解释。
2、快速幂 二进制
相信根据大神解释，已经了解基本运作类型，以下为代码：
1、速记、背诵版：
#include "bits/stdc++.h" using namespace std; #define ll long long ll Pow(int base,int exponent){ // base基数、exponent指数 ll result = 1; // 位运算 while(exponent>0){ if(exponent&1) // exponent与最低位进行运算 result *= base; base *= base; exponent>>=1; // 右移一位 } return result; } int main(){ // 如何求快速幂，对指数进行取余， ll num = Pow(2,4); cout<<num<<endl; return 0; } ---- 16
2、详细解释版：
// 包含一个非标准的头文件，它整合了几乎所有标准库的头文件 // 在竞赛等场景使用较为方便，但在正式项目中不推荐，因为会增加编译时间 #include "bits/stdc++.h" // 使用标准命名空间 std，这样在后续代码中使用标准库的类和函数时无需加 std:: 前缀 using namespace std; // 定义一个宏，将 ll 作为 long long 类型的别名 // 后续代码中使用 ll 就相当于使用 long long，简化代码书写 #define ll long long // 定义一个函数 Pow，用于计算 base 的 exponent 次幂 // base 是底数，即要进行乘方运算的数 // exponent 是指数，即表示乘方的次数 ll Pow(int base, int exponent) { // 初始化一个 long long 类型的变量 result 为 1 // 因为任何数的 0 次幂为 1，后续通过累乘来得到最终的幂结果 ll result = 1; // 开始一个 while 循环，只要指数 exponent 大于 0 就继续循环 // 该循环是实现快速幂算法的核心部分 while (exponent > 0) { // 使用按位与运算符 & 来判断 exponent 的二进制表示的最低位是否为 1 // 如果 exponent 的最低位是 1，那么 exponent & 1 的结果为 1，条件成立 // 例如，若 exponent 为 5（二进制 101），101 & 001 的结果为 1 if (exponent & 1) { // 当 exponent 的最低位为 1 时，说明当前这一位对应的 2 的幂次需要参与结果的计算 // 将当前的 base 乘到结果 result 中 result *= base; } // 将 base 进行平方操作 // 例如，第一次循环时 base 是原始值，第二次循环时 base 变为 base^2，第三次循环时 base 变为 base^4，以此类推 base *= base; // 将 exponent 右移一位，相当于将 exponent 除以 2 // 右移操作在二进制层面上把所有位向右移动一位，最右边的位被丢弃，左边补 0 // 例如，若 exponent 为 5（二进制 101），右移一位后变为 2（二进制 10） exponent >>= 1; } // 当 exponent 变为 0 时，循环结束，此时 result 即为 base 的 exponent 次幂的结果，将其返回 return result; } // 主函数，程序的入口点，程序从这里开始执行 int main() { // 调用 Pow 函数计算 2 的 4 次幂，并将结果存储在 long long 类型的变量 num 中 ll num = Pow(2, 4); // 使用 cout 输出计算得到的结果 num，并换行 // cout 是标准输出流对象，用于向控制台输出信息 cout << num << endl; // 主函数返回 0，表示程序正常结束 // 在 C++ 中，主函数返回 0 通常表示程序成功执行完毕 return 0; }
快速幂演变至今，不可能只有这么一种方法，接下来介绍另一种方法快速幂-指数折半-大神解释
3、快速幂 指数折半
相信根据大神解释，已经了解基本运作类型，以下为代码：
1、速记、背诵版本：
#include "bits/stdc++.h" using namespace std; #define ll long long ll Pow(int base, int exponent){ ll result = 1; while(exponent>0){ // 分奇、偶 if(exponent%2==1){// 奇数 exponent -= 1; exponent /= 2; result *= base; base *= base; }else{ // 偶数 exponent = exponent/2; base *= base; } } return result; } int main(){ // 如何求快速幂，对指数进行取余， ll num = Pow(2,4); cout<<num<<endl; return 0; } --- 16
2、详细解释版：
// 包含几乎所有标准库的头文件，在竞赛等场景中方便使用各种标准库功能 #include "bits/stdc++.h" // 使用标准命名空间，这样在代码中使用标准库的类和函数时可以省略 std:: 前缀 using namespace std; // 定义一个宏，将 ll 作为 long long 类型的别名，方便后续使用长整型 #define ll long long // 定义一个函数 Pow，用于计算 base 的 exponent 次幂 // base 是底数，即要进行乘方运算的数 // exponent 是指数，即表示乘方的次数 ll Pow(int base, int exponent){ // 初始化结果变量 result 为 1，因为任何数的 0 次幂为 1，后续用于累乘得到最终结果 ll result = 1; // 当指数 exponent 大于 0 时，继续循环进行幂运算 while(exponent>0){ // 根据指数的奇偶性进行不同处理 // 分奇、偶 if(exponent%2==1){// 奇数 // 若指数为奇数，先将指数减 1 变为偶数 exponent -= 1; // 再将指数除以 2 exponent /= 2; // 由于当前指数为奇数，此时需要将当前的 base 乘到结果 result 中 result *= base; // 将 base 平方，为下一次计算做准备，相当于让 base 的幂次翻倍 base *= base; }else{ // 偶数 // 若指数为偶数，直接将指数除以 2 exponent = exponent/2; // 将 base 平方，为下一次计算做准备，相当于让 base 的幂次翻倍 base *= base; } } // 循环结束后，result 即为 base 的 exponent 次幂的结果，将其返回 return result; } // 主函数，程序的入口点 int main(){ // 调用 Pow 函数计算 2 的 4 次幂，并将结果存储在变量 num 中 // 如何求快速幂，对指数进行取余， ll num = Pow(2,4); // 输出计算得到的结果 cout<<num<<endl; // 程序正常结束，返回 0 表示成功 return 0; }
4、竞赛
要知道，直接调用标准库函数，代码简洁。也就是 cmath 中的 pow()。
但是 pow() 存在两个缺点
- pow() 函数的实现通常涉及对数和指数的计算，时间复杂度较高，不适合处理大指数的幂运算。
- 浮点数运算可能会引入精度误差。
所以不推荐使用cmath中的pow()。而推荐使用cmath。
四、练习：
1、数的幂次
题目描述
给定三个正整数 N,M,PN,M,P，求 NMmodpNMmodp。
输入描述
第 11 行为一个整数 TT，表示测试数据数量。
接下来的 TT 行每行包含三个正整数 N,M,PN,M,P。
1≤T≤1051≤T≤105，1≤N,M,P≤1091≤N,M,P≤109。
输出描述
输出共 TT 行，每行包含一个整数，表示答案。
输入输出样例
示例 1
输入
3 2 3 7 4 5 6 5 2 9
输出
1 4 7
#include <iostream> #define ll long long // 必须要开到long long，否则会报错 using namespace std; ll quick(ll n, ll m, ll p){ ll res = 1; while(m){ if(m&1ll) res=(res*n)%p; // 1ll 也可以写成1,1ll代表为long long n=(n*n)%p; m>>=1; } return res; } int main() { int t; cin>>t; while(t--){ ll n,m,p; cin>>n>>m>>p; cout<<quick(n,m,p)<<endl; } return 0; }
2、小数第n位
题目描述
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个 0，它们就有了统一的形式。
本题的任务是：在上面的约定下，求整数除法小数点后的第 n 位开始的 3 位数。
输入描述
输入一行三个整数：a b n，用空格分开。a 是被除数，b 是除数，n 是所求的小数后位置（0<a,b,n<10^9）
输出描述
输出一行 3 位数字，表示：a 除以 b，小数后第 n 位开始的 3 位数字。
输入输出样例
示例
输入
1 8 1
输出
125
思路：
本题的主要思路是，通过乘10，把小数一个接一个的拉上来。并通过取模削减数字，防止溢出。
最重要的是，取模对本题中的除法运算没影响。
#include "bits/stdc++.h" #define ll long long using namespace std; // getNum 通过快速幂-二进制 ll getNum(ll a, ll b, ll p){ // a底数，b指数，p除数 ll res = 1; while(b){ // b是位数 if(b&1) res=(res*a)%p; // a*=(a%p); -> 这样是错的，会导致快速幂出错 a = a*a%p; b>>=1; // 右移一位 } return res; } int main() { // 输入数字 ll a,b,n; cin>>a>>b>>n; // a是除数、b是被除数、n是位数 // 进入这一步之前，有一点需要理清，取余不影响小数计算结果。 a = a*getNum(10,n-1,b); // 获得第n位的前一位。 a = a%b; // 第二核心 for(int i=0; i<3; ++i){ // 取3位 a*=10; cout<<a/b; a%=b; } return 0; }
3、堆的计数
好遗憾，这道题笔者咱无法解答，待后续有能力之后，在解决。
本题涉及了（组合数、费马小定理、逆元、阶乘、动态规划...），后续解决在给出答案
编辑
笔者感悟：
在这么整理多篇算法博客的途中，我发现算法难，大多时候不是因为你不会这道题，而是因为读不懂答案！我准备用带入法测试（普通题目：取一个数字测试。递归：画图法），后续博客发表测试效果。
借鉴博客/网站：
4、ACM数论之旅6---数论倒数，又称逆元（我整个人都倒了(￣﹏￣)）
