快速幂专题练习 ——基于罗勇军老师的《蓝桥杯算法入门C/C++》
一、P1226 【模板】快速幂 - 洛谷
方法一：算法代码（分治算法）
#include <bits/stdc++.h> // 包含几乎所有标准库的头文件（非标准，但常见于竞赛编程）
using namespace std; // 使用标准命名空间，避免每次调用标准库函数或对象时需要写 std::
typedef long long ll; // 定义 long long 类型的别名为 ll，方便使用
// 定义一个快速幂函数 fastPow，计算 a^n % m
ll fastPow(ll a, ll n, ll m) {
if (n == 0) { // 如果指数 n 为 0，任何数的 0 次幂都是 1
return 1;
}
if (n == 1) { // 如果指数 n 为 1，直接返回 a % m
return a % m;
}
ll t = fastPow(a, n / 2, m); // 递归计算 a^(n/2) % m，并将结果存储在 t 中
if (n % 2 == 1) { // 如果 n 是奇数
return (t % m * t % m) * a % m; // 返回 (t^2 % m) * a % m
} else { // 如果 n 是偶数
return t % m * t % m; // 返回 t^2 % m
}
}
// 主函数
int main() {
ll a, n, m; // 定义三个 long long 类型的变量 a, n, m
cin >> a >> n >> m; // 从标准输入读取 a, n, m 的值
printf("%lld^%lld mod %lld= %lld", a, n, m, fastPow(a, n, m)); // 输出 a^n % m 的结果
return 0; // 程序正常结束
}1. 代码目标
实现一个快速幂算法，计算 a^n % m 的值，并输出结果。快速幂算法通过减少乘法次数来优化计算效率，时间复杂度为 O(logn)。
2. 代码结构
代码分为两部分：
-
快速幂函数
fastPow：实现快速幂算法的核心逻辑。 -
主函数
main：处理输入和输出，调用fastPow函数计算结果。
3. 快速幂函数 fastPow 的设计思路
3.1 递归思想
快速幂算法的核心思想是分治法：
-
将问题分解为更小的子问题。
-
通过递归解决子问题，然后合并结果。
3.2 具体逻辑
-
递归终止条件：
-
如果 n=0，任何数的 0 次幂都是 1，直接返回 1。
-
如果 n=1，直接返回 a^n % m。
-
-
递归分解：
-
合并结果：
-
如果 n是奇数，返回 (t×t mod m)×a mod m。
-
如果 n是偶数，返回 t×t mod m。
-
3.3 模运算优化
-
每次乘法运算后都对 mm 取模，避免数值溢出。
-
例如，
t % m * t % m可以优化为(t * t) % m，因为t已经是fastPow的返回值，已经对 mm 取过模。
4. 主函数 main 的设计思路
4.1 输入处理
-
定义三个变量 a、n、，分别表示底数、指数和模数。
-
使用
cin从标准输入读取 a、n、m 的值。
4.2 调用快速幂函数
-
调用
fastPow(a, n, m)计算 a^n % m。
4.3 输出结果
-
使用
printf格式化输出结果，格式为：a^n mod m = 结果。
4.4 程序结束
-
返回 0，表示程序正常结束。
方法二：算法代码（快速幂）
#include<bits/stdc++.h> // 包含几乎所有标准库的头文件（非标准，但常见于竞赛编程）
using namespace std; // 使用标准命名空间，避免每次调用标准库函数或对象时需要写 std::
typedef long long ll; // 定义 long long 类型的别名为 ll，方便使用
// 定义一个快速幂函数 fastPow，计算 a^n % m
ll fastPow(ll a, ll n, ll m)
{
ll ans = 1; // 初始化结果为 1
a %= m; // 对 a 取模，确保 a 的值小于 m，避免后续计算溢出
// 使用循环计算快速幂
while (n) // 当 n 不为 0 时继续循环
{
if (n & 1) // 如果 n 的最低位是 1（即 n 是奇数）
{
ans = (ans * a) % m; // 将当前的 a 乘到结果中，并对 m 取模
}
a = (a * a) % m; // 将 a 平方，并对 m 取模
n >>= 1; // 将 n 右移一位，相当于 n = n / 2
}
return ans; // 返回最终结果
}
// 主函数
int main() {
ll a, n, m; // 定义三个 long long 类型的变量 a, n, m
cin >> a >> n >> m; // 从标准输入读取 a, n, m 的值
printf("%lld^%lld mod %lld= %lld", a, n, m, fastPow(a, n, m)); // 输出 a^n % m 的结果
return 0; // 程序正常结束
}1. 代码目标
实现一个快速幂算法，计算 a^n % m 的值，并输出结果。快速幂算法通过迭代法减少乘法次数，将时间复杂度从 O(n)优化到 O(logn)。
2. 代码结构
代码分为两部分：
-
快速幂函数
fastPow：实现快速幂算法的核心逻辑。 -
主函数
main：处理输入和输出，调用fastPow函数计算结果。
3. 快速幂函数 fastPow 的设计思路
3.1 迭代思想
快速幂算法的核心思想是通过二进制分解将幂运算转化为多个平方运算，从而减少乘法次数。
3.2 具体逻辑
-
初始化：
-
定义变量
ans并初始化为 1，用于存储最终结果。 -
对 a 取模，确保 a 的值小于 m，避免后续计算溢出。
-
-
循环计算：
-
使用
while循环，当 n 不为 0 时继续循环。 -
在每次循环中：
-
检查 n 的最低位是否为 1（即 n 是否为奇数）：
-
如果是奇数，将当前的 a 乘到
ans中，并对 m 取模。
-
-
将 a 平方，并对 m 取模。
-
将 n 右移一位，相当于 n=n/2。
-
-
-
返回结果：
-
循环结束后，返回
ans作为最终结果。
-
4. 主函数 main 的设计思路
4.1 输入处理
-
定义三个变量 a、n、m，分别表示底数、指数和模数。
-
使用
cin从标准输入读取 a、n、m 的值。
4.2 调用快速幂函数
-
调用
fastPow(a, n, m)计算 a^n % m。
4.3 输出结果
-
使用
printf格式化输出结果，格式为：a^n mod m = 结果。
4.4 程序结束
-
返回 0，表示程序正常结束。
5. while 循环的设计
5.1 循环条件
-
while (n)：
当 n 不为 0 时继续循环。每次循环将 n 右移一位，直到 n 变为 0。
5.2 循环体的设计
-
检查最低位是否为 1：
-
if (n & 1)：
检查 n 的最低位是否为 1（即 n 是否为奇数）。如果是 1，说明当前二进制位需要参与计算。 -
ans = (ans * a) % m;：
将当前的 a 乘到结果ans中，并对 m 取模。这一步相当于累乘二进制位为 1 的权重。
-
-
更新 a 的值：
-
a = (a * a) % m;：
将 a 平方，并对 m 取模。这一步相当于计算 a^2^k，为下一次循环做准备。
-
-
右移 n：
-
n >>= 1;：
将 n 右移一位，相当于 n=n/2。这一步用于逐步处理 n 的二进制位。
-
6. 为什么这样设计？
6.1 二进制分解
-
通过每次右移 nn，可以逐位检查 nn 的二进制表示。
-
如果某一位为 1，说明当前的 a2ka2k 需要参与计算。
6.2 平方运算
-
每次循环将 aa 平方，相当于计算 a2ka2k。
-
这样可以将幂运算转化为多个平方运算的乘积，减少乘法次数。
6.3 模运算
-
每次乘法运算后都对 mm 取模，避免数值溢出。
-
例如，
ans = (ans * a) % m和a = (a * a) % m。
7. 示例分析
示例：计算 3^13mod 5
-
初始化：
-
a=3, n=13, m=5.
-
ans = 1.
-
-
循环过程：
-
第一次循环：
-
n=13（二进制：
1101），最低位为 1。 -
ans = (1 * 3) % 5 = 3. -
a=(3∗3).
-
n=13>>1=6.
-
-
第二次循环：
-
n=6（二进制：
110），最低位为 0。 -
不更新
ans。 -
a=(4∗4).
-
n=6>>1=3.
-
-
第三次循环：
-
n=3（二进制：
11），最低位为 1。 -
ans = (3 * 1) % 5 = 3. -
a=(1∗1).
-
n=3>>1=1.
-
-
第四次循环：
-
n=1（二进制：
1），最低位为 1。 -
ans = (3 * 1) % 5 = 3. -
a=(1∗1).
-
n=1>>1=0.
-
-
-
结果：
-
循环结束，返回
ans = 3。 -
即 3^13mod 5=3。
-
二、P3197 [HNOI2008] 越狱 - 洛谷
算法代码：
#include<bits/stdc++.h> // 包含几乎所有标准库的头文件（非标准，但常见于竞赛编程）
using namespace std; // 使用标准命名空间，避免每次调用标准库函数或对象时需要写 std::
typedef long long ll; // 定义 long long 类型的别名为 ll，方便使用
// 定义一个快速幂函数 fastPow，计算 a^n % m
ll fastPow(ll a, ll n, ll m)
{
ll ans = 1; // 初始化结果为 1
a %= m; // 对 a 取模，确保 a 的值小于 m，避免后续计算溢出
// 使用循环计算快速幂
while (n) // 当 n 不为 0 时继续循环
{
if (n & 1) // 如果 n 的最低位是 1（即 n 是奇数）
{
ans = (ans * a) % m; // 将当前的 a 乘到结果中，并对 m 取模
}
a = (a * a) % m; // 将 a 平方，并对 m 取模
n >>= 1; // 将 n 右移一位，相当于 n = n / 2
}
return ans; // 返回最终结果
}
// 主函数
int main()
{
ll n, m; // 定义两个 long long 类型的变量 n 和 m
cin >> n >> m; // 从标准输入读取 n 和 m 的值
ll mod = 100003; // 定义模数 mod 为 100003
// 计算 ans = m^n % mod - (m % mod) * (m-1)^(n-1) % mod
ll ans = fastPow(m, n, mod) - m % mod * fastPow(m - 1, n - 1, mod) % mod;
// 如果 ans 为负数，调整结果使其为正数
if (ans < 0)
{
ans += mod; // 加上 mod，确保结果在 [0, mod-1] 范围内
}
return 0; // 程序正常结束
}1. 代码目标
计算表达式：
其中 mod=100003，并确保最终结果 ans 是非负数。
2. 代码结构
代码分为两部分：
-
快速幂函数
fastPow：实现快速幂算法的核心逻辑。 -
主函数
main：处理输入和输出，调用fastPow函数计算结果。
3. 快速幂函数 fastPow 的设计思路
3.1 迭代思想
快速幂算法的核心思想是通过二进制分解将幂运算转化为多个平方运算，从而减少乘法次数。
3.2 具体逻辑
-
初始化：
-
定义变量
ans并初始化为 1，用于存储最终结果。 -
对 a 取模，确保 a 的值小于 m，避免后续计算溢出。
-
-
循环计算：
-
使用
while循环，当 n 不为 0 时继续循环。 -
在每次循环中：
-
检查 n 的最低位是否为 1（即 nn 是否为奇数）：
-
如果是奇数，将当前的 a 乘到
ans中，并对 m 取模。
-
-
将 a 平方，并对 m 取模。
-
将 n 右移一位，相当于 n=n/2。
-
-
-
返回结果：
-
循环结束后，返回
ans作为最终结果。
-
4. 主函数 main 的设计思路
4.1 输入处理
-
定义两个变量 n 和 m，分别表示输入的参数。
-
使用
cin从标准输入读取 n 和 m 的值。
4.2 定义模数
-
定义模数 mod=100003。
4.3 计算表达式
-
计算表达式：
-
使用
fastPow函数计算 m^n mod mod。 -
使用
fastPow函数计算 (m−1)^(n−1) mod mod。 -
将两部分结果相减，并对 mod 取模。
-
4.4 调整结果为非负数
-
如果 ans 为负数，说明减法结果超出了模数的范围。
-
通过加上 mod，确保结果在 [0,mod−1] 范围内。
4.5 程序结束
-
返回 0，表示程序正常结束。
三、1.小数第n位 - 蓝桥云课
算法代码：
#include <bits/stdc++.h> // 包含几乎所有标准库的头文件（非标准，但常见于竞赛编程）
using namespace std; // 使用标准命名空间，避免每次调用标准库函数或对象时需要写 std::
typedef long long ll; // 定义 long long 类型的别名为 ll，方便使用
// 定义一个快速幂函数 fastPow，计算 a^n % m
ll fastPow(ll a, ll n, ll m)
{
ll ans = 1; // 初始化结果为 1
a %= m; // 对 a 取模，确保 a 的值小于 m，避免后续计算溢出
// 使用循环计算快速幂
while (n) // 当 n 不为 0 时继续循环
{
if (n & 1) // 如果 n 的最低位是 1（即 n 是奇数）
{
ans = (ans * a) % m; // 将当前的 a 乘到结果中，并对 m 取模
}
a = (a * a) % m; // 将 a 平方，并对 m 取模
n >>= 1; // 将 n 右移一位，相当于 n = n / 2
}
return ans; // 返回最终结果
}
// 主函数
int main()
{
ll a, b, n; // 定义三个 long long 类型的变量 a, b, n
cin >> a >> b >> n; // 从标准输入读取 a, b, n 的值
// 计算 x = a * 10^(n-1) % b
ll x = a * fastPow(10, n - 1, b) % b;
// 输出 x / b 的整数部分（即小数点后第一位）
cout << 10 * x / b;
// 更新 x 为 10 * x % b，计算小数点后第二位
x = 10 * x % b;
cout << 10 * x / b;
// 更新 x 为 10 * x % b，计算小数点后第三位
x = 10 * x % b;
cout << 10 * x / b;
return 0; // 程序正常结束
}结论：
- 在开始计算小数点后面的商时，实际上是连续求余，即余数乘以10然后对除数求余。
- 第n-1次的余数为x(n-1)=10^(n-1)x mod b（快速幂去模）,第n次的商为y(n)=10x(n-1)/b。
代码逻辑说明
1. 快速幂函数 fastPow
-
ll ans = 1;
初始化结果为 1，因为任何数的 0 次幂都是 1。 -
a %= m;
对 a 取模，确保 a 的值小于 m，避免后续计算中数值过大导致溢出。 -
while (n)
循环条件是 n 不为 0。每次循环将 n 右移一位，直到 nn 变为 0。 -
if (n & 1)
检查 n 的最低位是否为 1（即 n 是否为奇数）。如果是奇数，需要将当前的 a 乘到结果中。 -
ans = (ans * a) % m;
将当前的 a 乘到结果中，并对 m 取模，确保结果不会溢出。 -
a = (a * a) % m;
将 a 平方，并对 m 取模，为下一次循环做准备。 -
n >>= 1;
将 n 右移一位，相当于 n=n/2，用于逐步减小问题规模。 -
return ans;
返回最终的计算结果。
2. 主函数 main
-
ll a, b, n;
定义三个变量 a、b、n，分别表示输入的参数。 -
cin >> a >> b >> n;
从标准输入读取 a、b、n 的值。 -
ll x = a * fastPow(10, n - 1, b) % b;
计算 x=a×10^(n−1)mod b。这一步的目的是将 a 乘以 10^(n−1)后对 b 取模，得到一个小数部分的起始值。 -
cout << 10 * x / b;
输出 10×x/b 的整数部分，即小数点后第一位。 -
x = 10 * x % b;
更新 x 为 10×x mod b，用于计算小数点后第二位。 -
cout << 10 * x / b;
输出 10×x/b的整数部分，即小数点后第二位。 -
x = 10 * x % b;
更新 x 为 10×x mod b，用于计算小数点后第三位。 -
cout << 10 * x / b;
输出 10×x/b 的整数部分，即小数点后第三位。 -
return 0;
程序正常结束。
四、1.数的幂次 - 蓝桥云课
算法代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 快速幂函数，计算 n^m % p
ll fastPow(ll n, ll m, ll p)
{
ll ans = 1; // 初始化结果为 1
n %= p; // 对 n 取模，确保 n 的值小于 p，避免后续计算溢出
// 使用循环计算快速幂
while (m) // 当 m 不为 0 时继续循环
{
if (m & 1) // 如果 m 的最低位是 1（即 m 是奇数）
{
ans = (ans * n) % p; // 将当前的 n 乘到结果中，并对 p 取模
}
n = (n * n) % p; // 将 n 平方，并对 p 取模
m >>= 1; // 将 m 右移一位，相当于 m = m / 2
}
return ans; // 返回最终结果
}
int main()
{
ll t, n, m, p;
cin >> t; // 读取测试数据数量
while (t--) // 处理每组测试数据
{
cin >> n >> m >> p; // 读取 n, m, p
cout << fastPow(n, m, p) << endl; // 输出 n^m % p 的结果
}
return 0; // 程序正常结束
}代码逻辑说明
1. 快速幂函数 fastPow
-
ll ans = 1;
初始化结果为 1，因为任何数的 0 次幂都是 1。 -
n %= p;
对 n 取模，确保 n 的值小于 p，避免后续计算中数值过大导致溢出。 -
while (m)
循环条件是 m 不为 0。每次循环将 m 右移一位，直到 m 变为 0。 -
if (m & 1)
检查 m 的最低位是否为 1（即 m 是否为奇数）。如果是奇数，需要将当前的 n 乘到结果中。 -
ans = (ans * n) % p;
将当前的 n 乘到结果中，并对 p 取模，确保结果不会溢出。 -
n = (n * n) % p;
将 n 平方，并对 p 取模，为下一次循环做准备。 -
m >>= 1;
将 m 右移一位，相当于 m=m/2，用于逐步减小问题规模。 -
return ans;
返回最终的计算结果。
2. 主函数 main
-
ll t, n, m, p;
定义变量 t（测试数据数量）和 n,m,p（每组测试数据的输入）。 -
cin >> t;
读取测试数据数量。 -
while (t--)
循环处理每组测试数据。 -
cin >> n >> m >> p;
读取每组测试数据的 n,m,p。 -
cout << fastPow(n, m, p) << endl;
调用fastPow函数计算 n^m mod p，并输出结果。 -
return 0;
程序正常结束。
五、1.RSA解密 - 蓝桥云课
算法代码：
#include <iostream> // 包含输入输出流库
using namespace std; // 使用标准命名空间，避免每次调用标准库函数或对象时需要写 std::
typedef long long ll; // 定义 long long 类型的别名为 ll，方便使用
// 快速幂模运算函数，计算 a^b % mod
ll pow_mod(ll a, ll b, ll mod) {
ll res = 1; // 初始化结果为 1
while (b) { // 当 b 不为 0 时继续循环
if (b & 1) // 如果 b 的最低位是 1（即 b 是奇数）
res = (__int128)res * a % mod; // 将当前的 a 乘到结果中，并对 mod 取模
a = (__int128)a * a % mod; // 将 a 平方，并对 mod 取模
b >>= 1; // 将 b 右移一位，相当于 b = b / 2
}
return res; // 返回最终结果
}
int main() {
// 定义变量 n, d, C
ll n = 1001733993063167141LL; // 模数 n
ll d = 212353; // 私钥 d
ll C = 20190324; // 密文 C
// 分解 n 得到的质因数 p 和 q
ll p = 1123984201LL; // 质因数 p
ll q = 891234941LL; // 质因数 q
// 计算 φ(n) = (p - 1) * (q - 1)
ll phi = (p - 1) * (q - 1); // 欧拉函数 φ(n)
// 扩展欧几里得算法求模逆元 e
ll e = 823816093931522017LL; // 预计算的 e 值（公钥）
// 计算原文 X = C^e mod n
ll X = pow_mod(C, e, n); // 使用快速幂模运算计算 X
// 输出结果
cout << X << endl; // 输出结果：579706994112328949
return 0; // 程序正常结束
}六、1.子集选取 - 蓝桥云课
算法代码：
#include<bits/stdc++.h> // 包含几乎所有标准库的头文件（非标准，但常见于竞赛编程）
#define ll long long // 定义 long long 类型的别名为 ll，方便使用
using namespace std; // 使用标准命名空间，避免每次调用标准库函数或对象时需要写 std::
const ll mod = 1000000007; // 定义模数 mod 为 1000000007
ll n, m; // 定义两个 long long 类型的变量 n 和 m
// 快速幂函数，计算 x^k % mod
inline ll ksm(ll x, ll k) {
ll tmp = 1; // 初始化结果为 1
while (k) { // 当 k 不为 0 时继续循环
if (k % 2 == 1) // 如果 k 的最低位是 1（即 k 是奇数）
tmp *= x, tmp %= mod; // 将当前的 x 乘到结果中，并对 mod 取模
x = x * x % mod; // 将 x 平方，并对 mod 取模
k >>= 1; // 将 k 右移一位，相当于 k = k / 2
}
return tmp; // 返回最终结果
}
int main() {
cin >> n >> m; // 从标准输入读取 n 和 m 的值
cout << ksm(2, n * m); // 计算 2^(n*m) % mod 并输出结果
return 0; // 程序正常结束
}代码设计思路
1. 代码目标
计算 2^(n×m) mod 1000000007，并输出结果。
2. 代码结构
代码分为两部分：
-
快速幂函数
ksm：实现快速幂算法的核心逻辑。 -
主函数
main：读取输入并调用ksm函数计算结果。
3. 快速幂函数 ksm 的设计思路
-
初始化：
-
定义变量
tmp并初始化为 1，用于存储最终结果。
-
-
循环计算：
-
使用
while循环，当 kk 不为 0 时继续循环。 -
在每次循环中：
-
检查 k 的最低位是否为 1（即 kk 是否为奇数）：
-
如果是奇数，将当前的 x 乘到
tmp中，并对mod取模。
-
-
将 x 平方，并对
mod取模。 -
将 k 右移一位，相当于 k=k/2。
-
-
-
返回结果：
-
循环结束后，返回
tmp作为最终结果。
-
4. 主函数 main 的设计思路
-
读取输入：
-
从标准输入读取 n 和 m 的值。
-
-
调用快速幂函数：
-
调用
ksm(2, n * m)计算 2^(n×m) mod 1000000007。
-
-
输出结果：
-
输出计算结果。
-
-
程序结束：
-
返回 0，表示程序正常结束。
-
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
24
0- 0
已为社区贡献15条内容
所有评论(0)