【算法】acwing算法基础875.快速幂

题目

给定 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; // 初始化结果为 1 while (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; // 定义底数 a int b, p; // 定义指数 b 和模数 p // 输入 a, b, p scanf("%lld%d%d", &a, &b, &p); // 输出 a 的 b 次方模 p 的结果 cout << qmi(a, b, p) << endl; } return 0; }