【题目来源】
AcWing：876. 快速幂求逆元 - AcWing题库
【题目描述】
给定 \(n\) 组 \(a_i,p_i\)，其中 \(p_i\) 是质数，求 \(a_i\) 模 \(p_i\) 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 \(0\sim p-1\) 之间的逆元。
【输入】
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含一个数组 \(a_i,p_i\)，数据保证 \(p_i\) 是质数。
【输出】
输出共 \(n\) 行，每组数据输出一个结果，每个结果占一行。
若 \(a_i\) 模 \(p_i\) 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。
【输入样例】
3
4 3
8 5
6 3
【输出样例】
1
2
impossible
【算法标签】
《Acwing 876 快速幂求逆元》 #数学知识# #逆元# #快速幂# #费马小定理#
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef long long LL; // 定义长整型别名，防止乘法溢出/*** 快速幂算法：计算 a^k mod p* @param a 底数* @param k 指数* @param p 模数* @return a^k mod p 的结果*/
int qmi(int a, int k, int p)
{int res = 1; // 初始化结果为1（乘法单位元）// 使用二进制分解指数kwhile (k){// 如果当前二进制位为1，将a的当前幂次乘入结果if (k & 1){res = (LL)res * a % p; // 使用长整型防止乘法溢出}// 将a平方，准备处理下一位a = (LL)a * a % p;// 右移一位，处理下一个二进制位k >>= 1;}return res;
}int main()
{int n; // 测试用例数量scanf("%d", &n);// 处理每个测试用例while (n--){int a, p; // 输入参数：a为底数，p为模数scanf("%d%d", &a, &p);// 使用费马小定理计算a在模p下的乘法逆元// 逆元 = a^(p-2) mod pint res = qmi(a, p - 2, p);// 判断逆元是否存在：当且仅当a与p互质（即a不是p的倍数）if (a % p){// 逆元存在，输出结果printf("%d\n", res);}else{// 逆元不存在（a是p的倍数）puts("impossible");}}return 0;
}
【运行结果】
3
4 3
1
8 5
2
6 3
impossible