南昌做微信网站,医院网站建设网站,自己做流媒体网站难,东营做网站seo题目描述
输入b#xff0c;p#xff0c;k的值#xff0c;求b^p mod k的值#xff08;即b的p次方除以k的余数#xff09;。其中b#xff0c;p#xff0c;k*k为32位整数。
输入
输入b#xff0c;p#xff0c;k的值
输出
输出b^p mod k的值
样例输入
2 10 9
样例…题目描述
输入bpk的值求b^p mod k的值即b的p次方除以k的余数。其中bpk*k为32位整数。
输入
输入bpk的值
输出
输出b^p mod k的值
样例输入
2 10 9
样例输出
2^10 mod 97
方法一
分治策略求解
问题分析 递归方法: 使用递归函数 ans 来分解幂运算这是一种分治策略。递归方法允许将问题分解为更小的子问题这些子问题更容易解决。 处理基本情况: 当 p 等于 1 或 2 时有特定的返回条件这些是递归的基本情况。 偶数和奇数幂: 当 p 是偶数时b^p 可以分解为 (b^(p/2))^2。当 p 是奇数时b^p 可以分解为 (b^(p/2))^2 * b。 模运算的性质: 利用模运算的性质 (a * b) mod k ((a mod k) * (b mod k)) mod k 来避免中间结果过大。 递归的终止条件: 递归将持续进行直到 p 降至 1 或 2这时可以直接计算并返回结果。
#include bits/stdc.h
#define int long long // 使用长整型以支持大数运算
using namespace std;// 定义一个函数 ans 来计算 b^p mod k
int ans(int b, int p, int k) {// 如果幂 p 等于 1直接返回 b mod kif (p 1) {return b % k;}// 如果幂 p 等于 2返回 b^2 mod kif (p 2) {return b * b % k;}// 如果幂 p 是偶数if (p % 2 0) {// 递归计算 b^(p/2) mod kint m ans(b, p / 2, k);// 使用模运算的性质(a * a) mod k (a mod k * a mod k) mod kreturn m * m % k;} else {// 如果幂 p 是奇数// 先递归计算 b^(p/2) mod kint m ans(b, p / 2, k);// 然后再乘以 b并进行模运算return m * m % k * b % k;}
}signed main() {int b, p, k;cin b p k;printf(%lld^%lld mod %lld%lld, b, p, k, ans(b, p, k));
}
方法二
快速幂
问题分析
快速幂算法:
使用快速幂算法来高效地分解幂运算。 快速幂算法通过二进制展开指数 p 来减少计算量。
二进制分解:
指数 p 被分解为二进制形式算法通过迭代每个二进制位来累计结果。
迭代和模运算:
在每次迭代中如果当前的指数位为 1将相应的 b 的幂乘入结果。 b 每迭代一次进行平方并取模以保持结果在可管理的大小。
#include bits/stdc.h
#define int long long // 使用长整型以支持大数运算
using namespace std;signed main() {int b, p, k;cin b p k; // 读取基数 b指数 p 和模数 kint res 1; // 初始化结果为 1int by b, py p; // 保存原始的 b 和 p 值用于最后的输出// 快速幂算法while (p) {// 如果 p 的当前最低位是 1则将当前的 b 乘入结果if (p 1) res res * b % k;p 1; // 将 p 右移一位等同于 p 除以 2b b * b % k; // 将 b 平方后取模}// 输出结果printf(%lld^%lld mod %lld%lld, by, py, k, res);
}
