数学之快速幂-数的幂次

题目描述

给定三个正整数 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)。

---

快速幂的核心思想

1. 二进制分解：

   • 将指数 b 表示为二进制形式。例如，b=13的二进制表示为 1101。

   • 通过二进制分解，可以将  分解为多个 a 的幂的乘积。例如：

     

     其中，8,4,1是二进制位为 1 的位置对应的幂。

2. 分治法：

   • 通过不断平方 a，可以快速计算出  等幂。

   • 每次平方操作将幂的次数翻倍，从而大大减少计算量。

3. 模运算优化：

   • 在计算过程中，每一步都对结果取模 p，避免数值过大，同时保证结果的正确性。

---

快速幂的步骤

1. 初始化结果 res=1。

2. 检查指数 b 的二进制位：

   • 如果当前二进制位为 1，将当前的 a 乘到结果 res 中，并对 p 取模。

   • 将 a 平方，并对 p 取模，为下一次循环做准备。

   • 将 b 右移一位（相当于 b=b/2），继续处理下一位。

3. 当 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; // 程序正常结束
}