快速幂求逆元【通俗易懂 + 无需任何前置知识 + 不懂你打我】

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

注意：请返回在 0∼p−1 之间的逆元。乘法逆元的定义若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(modm)，则称 x 为 b 的模 m 乘法逆元，记为 b−1(mod m)。b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2 即为 b 的乘法逆元。

输入格式 第一行包含整数 n。 接下来 n 行，每行包含一个数组 ai,pi，数据保证 pi 是质数。

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

数据范围 1≤n≤105, 1≤ai,pi≤2∗109

这是逆元的本质：(可看可不看！) 逆元的定义： 假设 a 除 b，且a和b都是整数，非浮点数，那么我们希望不做除法，因为取余数的话除法很麻烦，所以我们希望把除法变成乘法，希望找到一个数，使得a/b的余数 == ax%m。 即对于某一个b，我们能够找到一个数x，使得a/b和ax模m的余数相同的话， 则把x记作b的模m的逆元，记作b的-1次方； 即b的逆元， b的-1次方，是一个整数，是一个标记。即我们可以把所有a/b的情况转化为a*b的逆元的情况下 % M；即把除法变成了整数。

** 草稿： ** 所以实际上本题就是给我一个b，然后让我找到一个x，使得bx % m 同余于1就可以了！ 即找到一个x，使得bx的乘积mod m 等于 1； 如果b是p的倍数，则b*x也一定是p的倍数，则模p一定不等于1的，就无解，若b不是p的倍数，那么由于p是质数，所以b只能是和p互质的，然后由费马定理可得b^p-1一定模p==1；一定存在逆元。