题目

给定 n 组 ai,bi,pi，对于每组数据，求出 ai^bi mod pi 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式

对于每组数据，输出一个结果，表示 ai^bi mod pi 的值。

每个结果占一行。

数据范围

1≤n≤100000

1≤ai,bi,pi≤2×109

输入样例：

2

3 2 5

4 3 9

输出样例：

4

1

来源：acwing算法基础875. 快速幂

---

思路（注意事项）

将b转为2进制，另外注意防止越界需要定义ans和 a为long long.

---

纯代码

#include<iostream>
using namespace std;typedef long long LL;int qmi (LL a, int b, int p)
{LL ans = 1;while (b){if(1&b) ans = ans * a % p;b >>= 1;a = a * a % p;}return ans;
}int main(){int n;cin >> n;while (n --){LL a;int b, p;scanf ("%lld%d%d", &a, &b, &p);cout << qmi (a, b, p) << endl;}return 0;
}

题解（带注释）

#include<iostream>
using namespace std;
typedef long long LL; // 定义 long long 的别名 LL// 定义一个函数 qmi，用于计算 a 的 b 次方模 p 的结果
int qmi(LL a, int b, int p)
{LL ans = 1; // 初始化结果为 1while (b) // 当 b 不为 0 时循环{if (1 & b) ans = ans * a % p; // 如果 b 的最低位为 1，将 a 乘到结果中b >>= 1; // 将 b 右移一位a = a * a % p; // 将 a 平方}return ans; // 返回最终结果
}int main(){int n; // 定义测试用例的数量cin >> n; // 输入测试用例的数量// 处理每个测试用例while (n --){LL a; // 定义底数 aint b, p; // 定义指数 b 和模数 p// 输入 a, b, pscanf("%lld%d%d", &a, &b, &p);// 输出 a 的 b 次方模 p 的结果cout << qmi(a, b, p) << endl;}return 0;
}