【快速幂】快速幂求逆元

题目

876. 快速幂求逆元 - AcWing题库

---

给定 $n$ 组 $a_i, p_i$ ，其中 $p_i$ 是质数，求 $a_i$ 模 $p_i$ 的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 $0 \sim p-1$ 之间的逆元。

乘法逆元的定义

若整数 $b，m$ 互质，并且对于任意的整数 $a$ ，如果满足 $b|a$ ，则存在一个整数 $x$ ，使得 $a/b≡a \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 \le n \le 10^5$ ,
$1 \le a_i,p_i \le 2*10^9$

输入样例：

3
4 3
8 5
6 3

输出样例：

1
2
impossible

解题

方法一：快速幂

逆元

定义

若整数 $b, p$ 互质^[1]，且对于任意一个整数 $a$ ，如果满足 $b \mid a$ ^[2] ，则存在一个整数 $x$ ，使得 $\frac{a}{b} \equiv a \cdot x \pmod p$ ^[3] 。称 $x$ 为 $b$ 在模 $p$ 意义下的乘法逆元，记作 $b^{-1} \pmod p$ 。

作用

在要除以一个数，再取模时，把除法变成乘法运算，然后再取模。

思路

根据逆元的定义，有： $\frac{a}{b} \equiv a \cdot b^{-1} \pmod p$ ；

两边同乘 $b$ 得： $a \equiv a \cdot b \cdot b^{-1} \pmod p$ ；

所以： $b \cdot b^{-1} \equiv 1 \pmod p$ ①；

根据费马小定理 ：若 $p$ 为质数且 $b, p$ 互质，则 $b^{p-1} \equiv 1 \pmod p$ 。

从上式 $b^{p-1}$ 中拆出一个 $b$ 得到： $b \cdot b^{p-2} \equiv 1 \pmod p$ 。

结合①式得到：$b^{-1} \equiv b^{p-2} \pmod p$ 。

综上，在 $b$ 存在乘法逆元的条件下，求出 $b^{p-2} \bmod p$ 即为 $b$ 在模 $p$ 意义下的乘法逆元。

使用快速幂求解即可。

注意：题目虽然保证 $p$ 为质数，但是并没有保证 $b, p$ 互质，所以在算之前要判断逆元是否存在。

代码

import java.util.*;
import java.io.*;

public class Main {
    static long quickPow(long base, long exp, long mod) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = res * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int p = (int) in.nval;
            System.out.println(a % p == 0 ? "impossible" : quickPow(a, p - 2, p));
        }
    }
}

---

1. $\gcd(b, m) = 1$ 。 ↩︎

2. $a$ 能被 $b$ 整除（ $\frac{a}{b}$ 是一个整数 ）。 ↩︎

3. $\frac{a}{b}$ 在模 $p$同余于 $a \cdot x$ （ $\frac{a}{b} \bmod p = a \cdot x \bmod p$ ）。 ↩︎