阅读本文所需前置知识：快速幂

# 数论中的逆元

乘法逆元：已知 b,m 互质，并且对于任意整数 a ，如果满足 b 可以整除 a （即 a 是 b 的倍数），则存在一个整数 x ，使得 $a/b \equiv a*x\pmod{m}$ ，则称 x 为 b 的模 m 乘法逆元，记为 $b^{-1}\pmod{m}$ 。 (注意这里的 - 1 作为一个标记，用来表示逆元，而非指数。)

b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时， $b^{m - 2}$ 即为 b 的乘法逆元。

# 逆元的推导

乘法逆元的作用是什么呢？

当 a,b 两个数很大时，想要求出 $a/b \pmod m$ 的值。

但是此时 $a/b \pmod m \ne ((a \bmod m) / (b \bmod m)) \bmod m$ 。

我们如果借助逆元，将 $a/b$ 转换为 $a*b^{-1} \bmod m$ （其中 $b^{-1}$ 为 b 的模 m 的乘法逆元）。

假设 b 的模 m 的逆元为 $b^{-1}$ ，那么可以得到公式：
$a*b^{-1} \pmod m = ((a \bmod m) * (b^{-1} \bmod m)) \bmod m$ 。

由此，我们就把较难计算 (可能产生小数) 的除法等价变换为乘法运算。

# 前置知识：同余定理

给出一个正整数 m ，如果两个整数 a 和 b 满足 a-b 能够被 m 整除，即 (a-b)/m 得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 $a\equiv b\pmod{m}$ 。

举个示例：
当 m=2,a=10,b=6 的时候，有 a-b=10-6=4 4%2==0 ，所以我们可以称为 10与6对于模2是同余的 ，记作 $10\equiv 6\pmod{2}$ 。

如果枯燥的定义难以理解的话，可以从名字本身记忆，同余即有相同的余数，也就是说 当a和b对于模m同余的话，a模m和b模m有相同的余数 。

同余定理是初等数论中的基础组成部分，非常重要。同余定理本身可以推导出很多的性质，本文后面需要用到的一个性质是：

如果 $ac\equiv bc\pmod{m}$ ，且 c 和 m 互质，则 $a\equiv b\pmod{m}$ 。

该性质是如何得到的呢？
通过定义可知： $(ac - bc) \bmod m == 0$ ，可以变形成 $c(a-b) \bmod m==0$ 。

而 c 与 m 互质说明了什么呢？说明了他们的最大公约数的是 1 ，因此 $c \bmod m$ 一定不是 0 ，那如何让 c 模 m 变成 0 呢？当然是乘以一个 m 的倍数。既， a-b 本身就是 m 的倍数。

举一个例子：
当 m=2,a=10,b=6,c=3 的时候，我们知道 c%m=3%2!=0 ，但是当 x 是任意 m 的倍数时候， 3*x%2==0 (此处的 x 为 a-b , 该例子中为 4 ) 就成立了。因此， x 已经是 m 的倍数了，所以 x%m 已经等于 0 了，去掉 c ，完全不影响等式正确性。

# 前置知识：费马小定理

如果 p 是一个质数，而整数 a 不是 p 的倍数，则有 $a^{p-1}\equiv 1 \pmod p$ 。

# 推导过程

根据上面同余定理的性质， b 与 m 是互质的，所以两面可以同时乘以 b ： $a/b \equiv a*x\pmod{m} \Longrightarrow a \equiv a*b*x\pmod{m}$ ；
因为 a 是 b 的倍数，而 b 又与 m 互质，因此对于 b 来说，一定也存在一个 a 与 m 互质，因此，再次利用同余定理的性质两边同时约去 a ，得到： $a\equiv a*b*x\pmod{m} \Longrightarrow 1\equiv b*x\pmod{m}$ ；
因为 b 与 m 是互质的，根据费马小定理，可知： $b^{m-1}\equiv 1 \pmod m$ ；
联立步骤 2、3 里面的公式，得到：$b^{m-1}\equiv b*x\pmod {m} $ ；
两面同时乘以 $b^{-1}$ ，得到：$b^{m-2}\equiv x\pmod {m} $ ；
根据同余的对称性，得到：$x \equiv b^{m-2} \pmod {m} $ ；

最后我们可以得到结论：当 b 与 m 互质，且 a 是 b 的倍数，且 m 是质数的情况下，我们可以得到 b的模m的逆元x 为： $b^{m-2} \bmod m$ 。

# Code

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

可以看到最终求逆元的公式可以直接套到快速幂上，因此每组数据的时间复杂度是 $O(log{(m-2}))$ 。

另外，注意到我们在推导公式的第二步，是通过 a 是 b 的倍数，而 b 又与 m 互质，推出一定会有 a 与 m 互质，从而约掉了等式两边的 a。但是注意到 m 是质数，而当 a 是 m 的倍数时，a 与 m 是不互质的，因此必须 $a\bmod m\ne0$ 的时候才有逆元，否则当 a 是 m 的倍数的时候是没有逆元的。

	#include <iostream>
	using namespace std;

	typedef long long LL;

	// 快速幂
	LL qmi(int a, int k, int p) {
	LL res = 1 % p;
	while (k) {
	if (k & 1) res = res * a % p;
	k >>= 1;
	a = a * (LL)a % p;
	}
	return res;
	}

	int main() {
	int n;
	scanf("%d", &n);
	while (n --) {
	int a, p;
	scanf("%d%d", &a, &p);
	//a % p != 0 说明 a,p 是互质的此时才有逆元
	if (a % p) printf("%lld\n", qmi(a, p - 2, p));
	else printf("%s\n", "impossible");
	}
	return 0;
	}