快速幂 | 取余运算
名人说：莫听穿林打叶声，何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》
本篇笔记整理：Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊）
以下内容，仅供学习交流，且仅在CSDN平台发布，未经授权禁止二次转发。
一、问题呈现
1.题目描述
给你三个整数 a , b , p a,b,p a,b,p，求 a b m o d p a^b \bmod p abmodp。
2.输入格式
输入只有一行三个整数，分别代表 a , b , p a,b,p a,b,p。
3.输出格式
输出一行一个字符串 a^b mod p=s，其中
a
,
b
,
p
a,b,p
a,b,p 分别为题目给定的值，
s
s
s 为运算结果。
4.样例
1️⃣样例输入 #1
2 10 9
2️⃣样例输出 #1
2^10 mod 9=7
提示
样例解释
2 10 = 1024 2^{10} = 1024 210=1024， 1024 m o d 9 = 7 1024 \bmod 9 = 7 1024mod9=7。
数据规模与约定
对于 100 % 100\% 100% 的数据，保证 0 ≤ a , b < 2 31 0\le a,b < 2^{31} 0≤a,b<231， a + b > 0 a+b>0 a+b>0， 2 ≤ p < 2 31 2 \leq p \lt 2^{31} 2≤p<231。
二、源码实现
#include <iostream>
using namespace std;
// 定义一个快速幂函数，返回 a^b mod p 的值
int fast_pow(int a, int b, int p) {
// 初始化结果为 1
int res = 1;
// 循环 b 次，每次将 a 乘到 res 上，并对 p 取余
while (b > 0) {
// 如果 b 是奇数，那么 res 需要乘上 a
if (b & 1) {
res = (long long)res * a % p;
}
// 将 a 平方，并对 p 取余
a = (long long)a * a % p;
// 将 b 右移一位，相当于除以 2
b >>= 1;
}
// 返回结果
return res;
}
int main() {
// 输入 a, b, p
int a, b, p;
cin >> a >> b >> p;
// 调用快速幂函数，得到结果 s
int s = fast_pow(a, b, p);
// 输出结果
cout << a << "^" << b << " mod " << p << "=" << s << endl;
return 0;
}
★关于本题思路：
本题在于对快速幂的使用，以及long long数据类型的考量。
①一般求幂常见用法
int pow(int a,int b) {
int ans;
for(int i = 1;i<=b;++i) {
ans*=a;
}
return ans;
}
原理十分简单，将a乘b次。 时间复杂度： O(n)
但快速幂比它更快，下面简单介绍一下快速幂的原理。
②快速幂
快速幂的原理：
快速幂算法的原理是利用二进制的性质，将一个整数 n 拆分为若干个二进制位，然后根据每一位是否为 1 来决定是否乘上相应的 a 的幂。
具体来说：
- 首先将 n 写成二进制的形式，例如 n = 13，那么 n = (1101)_2进制，表示 n = 2^3 + 2^2 + 2^0。
- 然后观察 n 的每一位，如果某一位为 1，那么就表示需要乘上 a 的相应的幂次，例如 n 的第 0 位为 1，那么就需要乘上 a^0 = 1；n 的第 2 位为 1，那么就需要乘上 a^2；n 的第 3 位为 1，那么就需要乘上 a^3。
- 最后将所有需要乘上的 a 的幂次相乘，就得到了 a^n 的值，例如 a^n = a^3 * a^2 * a^0。
这样做的好处是，可以减少乘法的次数，从 O(n) 降低到 O(log n)，因为只需要计算出 a, a^2, a^4, …, a(2k) 等幂次，其中 k 是 n 的二进制位数。而这些幂次可以通过不断地平方来得到，例如 a^2 = a * a, a^4 = (a^2) * (a^2), …, a(2k) = (a(2(k-1))) * (a(2(k-1)))。这样每次只需要判断 n 的当前末位是否为 1，然后决定是否乘上当前的 a 的幂次，然后将 a 平方，并将 n 右移一位，直到 n 为 0 时停止。
因此根据以上原理，我们可以有以下两种写法（包括但不仅限于此两种，但写法虽不同，思想是一致的：
1️⃣写法一
while(m>0){
if(m%2==1)
ans=ans * b % p;
b=b * b%p;
m=m>>1;
}
2️⃣写法二（本文采用了写法二，但是二者的算法实现的思想是一样的）
while (b > 0) {
// 如果 b 是奇数，那么 res 需要乘上 a
if (b & 1) {
res = (long long)res * a % p;
}
// 将 a 平方，并对 p 取余
a = (long long)a * a % p;
// 将 b 右移一位，相当于除以 2
b >>= 1;
}
// 返回结果
return res;
}
通过对快速幂算法的使用，成功将O(n)复杂度的求幂方式，转化为了时间复杂度为O(log n)的快速幂方式，效率成功得到了提升。文章来源：https://www.toymoban.com/news/detail-539653.html
三、测试结果
2 10 9
2^10 mod 9=7
--------------------------------
Process exited after 19.18 seconds with return value 0
请按任意键继续. . .
Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足的！ ღ( ´･ᴗ･` )文章来源地址https://www.toymoban.com/news/detail-539653.html
到了这里，关于C/C++提高篇——快速幂 | 取余运算 模板题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
