【快速幂】876.快速幂求逆元

876. 快速幂求逆元

文章目录 题目描述输入格式：输出格式：数据范围输入样例输出样例 方法：快速幂解题思路代码复杂度分析：

题目描述

给定 n 组 a i , p i a_i,p_i ai​,pi​，其中 p i p_i pi​ 是质数，求 a i a_i ai​ 模 p i p_i pi​ 的乘法逆元，若逆元不存在则输出 impossible。 注意：请返回在 0∼p−1 之间的逆元。 乘法逆元的定义

若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a / b ≡ a × x ( m o d   m ) a/b≡a×x(mod\ m) a/b≡a×x(mod m)，则称 x 为 b 的模 m 乘法逆元，记为 b − 1 ( m o d   m ) b^{−1}(mod\ m) b−1(mod m)。b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时， b m − 2 b^{m−2} bm−2 即为 b 的乘法逆元。

输入格式：

第一行包含整数 n。 接下来 n 行，每行包含一个数组 a i , p i a_i,p_i ai​,pi​，数据保证 p i p_i pi​ 是质数。

输出格式：

输出共 n n n 行，每组数据输出一个结果，每个结果占一行。 若 a i a_i ai​ 模 p i p_i pi​ 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

数据范围 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105 1 ≤ a i , p i ≤ 2 × 1 0 9 1≤a_i,p_i≤2\times10^9 1≤ai​,pi​≤2×109 输入样例 3 4 3 8 5 6 3 输出样例 1 2 impossible 方法：快速幂 解题思路

代码 #include <iostream> using namespace std; typedef long long LL; int n; LL qmi(int a, int k, int p) { LL res = 1; while(k) { if(k & 1) res = (LL)res * a % p; k >>= 1; a = (LL)a * a % p; } return res; } int main() { cin >> n; while(n--) { int a, p; cin >> a >> p; if(a % p == 0) puts("impossible"); else cout << qmi(a, p - 2, p) << endl; } return 0; } 复杂度分析： 时间复杂度： O ( n × l o g ( p − 2 ) ) O(n\times log(p-2)) O(n×log(p−2))空间复杂度： O ( 1 ) O(1) O(1)