64.Acwing基础课第875题-简单-快速幂
题目描述
\(给定 n 组 a_i,b_i,p_i，对于每组数据，求出 a_i^{b_i}mod\ p_i 的值。\)。
输入格式
\(第一行包含整数 n\)。
\(接下来 n 行，每行包含三个整数 a_i,b_i,p_i\)。
输出格式
\(对于每组数据，输出一个结果，表示a_i^{b_i}mod\ p_i 的值\)。
\(每个结果占一行\)。
数据范围
\(1≤n≤10^6\),
\(1≤a_i,b_i,p_i≤2×10^9\)
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
代码：
// 包含输入输出流头文件（cin/cout依赖，本代码用C风格输入输出，可保留）
#include <iostream>
// 算法库（本代码未直接使用，属于通用模板保留）
#include <algorithm>// 使用std命名空间，避免重复写std::
using namespace std;// 定义长整型别名：防止乘法过程中溢出（int相乘可能超出int范围）
typedef long long LL;// 快速幂核心函数：计算 (a^b) % p 的结果
// 原理：将指数b二进制分解，把O(b)的乘法优化为O(logb)，大幅提升效率
// 参数：a-底数，b-指数，p-模数
LL qmi(int a, int b, int p)
{// 初始化结果为 1%p：处理p=1的特殊情况（任何数模1都为0）LL res = 1 % p;// 二进制分解指数b：循环直到b的所有二进制位处理完毕while (b){// b & 1：判断b的二进制最低位是否为1（等价于b%2==1）// 若最低位为1，说明当前位需要参与乘法，结果乘以当前a并取模if (b & 1) res = res * a % p;// 底数平方：对应二进制指数左移一位（如a^1 → a^2，a^2 → a^4）// (LL)a：强制转换为长整型，避免a*a溢出int范围a = a * (LL)a % p;// 指数右移一位：等价于b = b / 2（舍弃最低位，处理下一位）b >>= 1;}// 返回最终的 (a^b) % p 结果return res;
}int main()
{int n; // n：测试用例的组数// C风格输入：比cin更快，适合大数据量场景scanf("%d", &n);// 循环处理n组测试用例while (n -- ){int a, b, p; // a-底数，b-指数，p-模数scanf("%d%d%d", &a, &b, &p); // 输入一组a,b,p// 调用快速幂函数，输出结果（%lld对应LL类型）printf("%lld\n", qmi(a, b, p));}return 0; // 程序正常结束
}