如何快速计算65题中65的逆元？

65.Acwing基础课第876题-简单-快速幂求逆元 题目描述 \(给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible\)。 注意：\(请返回在 0∼p−1 之间的逆元\)。 乘法逆元的定义 若整数 \(b, m\) 互质，并且对于任意的整数 \(a\)，如果满足 \(b|a\)，则存在一个整数 \(x\)，使得 \(\frac{a}{b} \equiv x \times x \pmod{m}\) ，称 \(x\) 为 \(b\) 的模 \(m\) 乘法逆元，记为 \(b^{-1} \pmod{m}\)。 \(b\) 存在乘法逆元的充要条件是 \(b\) 与模数 \(m\) 互质。当模数 \(m\) 为质数时，\(b^{m-2}\) 即为 \(b\) 的乘法逆元。 输入格式 \(第一行包含整数 n\)。 \(接下来 n 行，每行包含三个整数 a_i,p_i，数据保证 p_i 是质数\)。 输出格式 \(输出共 n 行，每组数据输出一个结果，每个结果占一行\)。 \(若 a_i 模 p_i 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible\)。 数据范围 \(1≤n≤10^5\), \(1≤a_i,p_i≤2×10^9\) 输入样例： 3 4 3 8 5 6 3 输出样例： 1 2 impossible 代码： // 包含输入输出流头文件（cin/cout依赖，本代码用C风格IO，保留作为通用模板） #include <iostream> #include <algorithm> using namespace std; // 定义长整型别名：防止乘法过程中溢出（int相乘可能超出int范围） typedef long long LL; // 快速幂核心函数：计算 (a^b) % p 的结果 // 用途：本题中用于计算费马小定理的 b^(p-2) mod p（乘法逆元） // 参数：a-底数，b-指数，p-模数（本题中p是质数） LL qmi(int a, int b, int p) { LL res = 1; // 初始化结果为1（乘法单位元） // 二进制分解指数b，循环处理每一位（时间复杂度O(logb)） while (b) { // b & 1：判断b的二进制最低位是否为1（等价于b%2==1） // 若为1，将当前底数的幂乘到结果中，并取模防止溢出 if (b & 1) res = res * a % p; // 底数平方：对应指数左移一位（如a^1→a^2，a^2→a^4） // (LL)a：强制转换为长整型，避免a*a溢出int范围（如a=1e9时，a²=1e18） a = a * (LL)a % p; // 指数右移一位：等价于b = b / 2，舍弃已处理的最低位 b >>= 1; } return res; // 返回 (a^b) % p 的结果 } int main() { int n; // n：测试用例的组数 // C风格输入：比cin更快，适合竞赛大数据量场景 scanf("%d", &n); // 循环处理n组测试用例 while (n -- ) { int a, p; // a：要求逆元的数；p：模数（题目保证p是质数） scanf("%d%d", &a, &p); // 乘法逆元存在的充要条件：a与p互质（p是质数时，等价于a%p≠0） if (a % p == 0) puts("impossible"); // a是p的倍数，无逆元，输出impossible else // 费马小定理：当p是质数且a与p互质时，a的乘法逆元 = a^(p-2) mod p printf("%lld\n", qmi(a, p - 2, p)); } return 0; // 程序正常结束 }