题解：AcWing 875 快速幂

【题目来源】

AcWing：875. 快速幂 - AcWing题库

【题目描述】

给定 \(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\) 的值。

每个结果占一行。

【输入样例】

2
3 2 5
4 3 9

【输出样例】

4
1

【算法标签

【代码详解】

《AcWing 875 快速幂》 #数学知识# #快速幂#

#include <bits/stdc++.h>
using namespace std;typedef long long LL;  // 定义长整型别名，防止乘法溢出// 快速幂算法：计算 a^k mod p
int qmi(int a, int k, int p)
{int res = 1;  // 初始化结果为1（a^0 = 1）// 当指数k不为0时循环while (k){// 如果当前最低位为1，将a乘入结果if (k & 1)res = (LL)res * a % p;  // 强制转换为LL防止溢出// a平方，准备处理下一位a = (LL)a * a % p;  // 强制转换为LL防止溢出// 右移一位，处理下一个二进制位k >>= 1;}return res;
}int main()
{int n;  // 查询次数scanf("%d", &n);// 处理每个查询while (n--){int a, k, p;  // 底数、指数、模数scanf("%d%d%d", &a, &k, &p);// 调用快速幂函数并输出结果printf("%d\n", qmi(a, k, p));}return 0;
}

【运行结果】

2
3 2 5
4
4 3 9
1