2923. 快速幂求逆元
时间限制：1000 MS 内存限制：128 MB
题目描述
# 快速幂求逆元 ## 题目描述 给定 $n$ 组整数 $a_i,p_i$，其中 $p_i$ 保证为质数。对于每组数据，求 $a_i$ 模 $p_i$ 的乘法逆元；若逆元不存在，则输出 `impossible`。 若整数 $x$ 满足 $$ a_i x \equiv 1 \pmod{p_i}, $$ 则称 $x$ 为 $a_i$ 模 $p_i$ 的乘法逆元。本题要求输出满足 $0 \le x \le p_i-1$ 的逆元，该范围内的逆元若存在则唯一。 整数 $a_i$ 存在模 $p_i$ 的乘法逆元，当且仅当 $a_i$ 与 $p_i$ 互质。当 $p_i$ 为质数且 $a_i$ 不为 $p_i$ 的倍数时，由费马小定理可得，其逆元为 $a_i^{p_i-2}$ 对 $p_i$ 取模的结果。 ## 输入格式 从文件 `inverse.in` 读入数据。 第一行包含一个整数 $n$，表示数据组数。 接下来 $n$ 行，每行包含两个整数 $a_i,p_i$，保证 $p_i$ 为质数。 ## 输出格式 将结果输出到文件 `inverse.out`。 输出共 $n$ 行，第 $i$ 行对应第 $i$ 组数据： - 若 $a_i$ 模 $p_i$ 的乘法逆元存在，输出满足 $0 \le x \le p_i-1$ 的逆元 $x$。 - 否则，输出 `impossible`。 ## 数据范围 - $1 \le n \le 10^5$。 - $1 \le a_i,p_i \le 2 \times 10^9$。 - $p_i$ 为质数。 ## 样例输入 ``` 3 4 3 8 5 6 3 ``` ## 样例输出 ``` 1 2 impossible ```