快速幂 | 取余运算
以下笔记内容，仅供学习交流，且仅在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;
}
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, …, ak) 等幂次，其中 k 是 n 的二进制位数。而这些幂次可以通过不断地平方来得到，例如 a^2 = a * a, a^4 = (a^2) * (a^2), …, ak) = (a(k-1))) * (a(k-1)))。这样每次只需要判断 n 的当前末位是否为 1，然后决定是否乘上当前的 a 的幂次，然后将 a 平方，并将 n 右移一位，直到 n 为 0 时停止。
因此根据以上原理，我们可以有以下两种写法（包括但不仅限于此两种，但写法虽不同，思想是一致的：
while(m>0){
if(m%2==1)
ans=ans * b % p;
b=b * b%p;
m=m>>1;
}
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)的快速幂方式，效率成功得到了提升。
三、测试结果
2 10 9
2^10 mod 9=7
--------------------------------
Process exited after 19.18 seconds with return value 0
请按任意键继续. . .