宁夏网站建设费用,网站开启gzip压缩,wordpress js插件开发,企业网络推广宣传方案题目描述
给定三个正整数 N,M,P#xff0c;求
输入描述
第 1 行为一个整数 T#xff0c;表示测试数据数量。
接下来的 T 行每行包含三个正整数 N,M,P。 输出描述
输出共 T 行#xff0c;每行包含一个整数#xff0c;表示答案。
输入输出样例
示例 1 输入 3
2 3 7
4…题目描述
给定三个正整数 N,M,P求
输入描述
第 1 行为一个整数 T表示测试数据数量。
接下来的 T 行每行包含三个正整数 N,M,P。 输出描述
输出共 T 行每行包含一个整数表示答案。
输入输出样例
示例 1 输入 3
2 3 7
4 5 6
5 2 9输出 1
4
7
思想
快速幂Fast Exponentiation是一种用于高效计算大整数幂运算的算法特别是在计算 时非常有用。它的核心思想是通过分治法和二进制分解将幂运算的时间复杂度从 O(b) 降低到O(logb)。 快速幂的核心思想 二进制分解 将指数 b 表示为二进制形式。例如b13的二进制表示为 1101。 通过二进制分解可以将 分解为多个 a 的幂的乘积。例如 其中8,4,1是二进制位为 1 的位置对应的幂。 分治法 通过不断平方 a可以快速计算出 等幂。 每次平方操作将幂的次数翻倍从而大大减少计算量。 模运算优化 在计算过程中每一步都对结果取模 p避免数值过大同时保证结果的正确性。 快速幂的步骤 初始化结果 res1。 检查指数 b 的二进制位 如果当前二进制位为 1将当前的 a 乘到结果 res 中并对 p 取模。 将 a 平方并对 p 取模为下一次循环做准备。 将 b 右移一位相当于 bb/2继续处理下一位。 当 b 变为 0 时返回结果 res。
解题代码
#include bits/stdc.h
using namespace std;
typedef long long ll;// 定义一个快速幂函数 qmi用于计算 a^b % p
ll qmi(ll a, ll b, ll p)
{ll res 1; // 初始化结果为 1while (b) // 当 b 不为 0 时循环{if (b 1) // 如果 b 的最低位是 1res res * a % p; // 将当前的 a 乘到结果中并取模 pa a * a % p; // 将 a 平方并取模 pb 1; // 将 b 右移一位相当于 b / 2}return res; // 返回最终结果
}int main()
{int t; // 定义测试用例的数量 tcin t; // 输入测试用例的数量for (int i 1; i t; i) // 循环处理每个测试用例{ll n, m, p; // 定义三个正整数 n, m, pcin n m p; // 输入 n, m, pcout qmi(n, m, p) \n; // 调用 qmi 函数计算 n^m % p 并输出结果}return 0; // 程序正常结束
}
