题目描述

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

注意：请返回在0∼p−1之间的逆元。

乘法逆元的定义 若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b−1(mod m)。

b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，bm−2即为b的乘法逆元。 








注： b|a 就是 a % b ==0 


        a/b≡a∗x(mod m) 就是  (a / b) % m == (a * x) % m 








关于快速幂： https://www.bilibili.com/video/BV1FJ411R7Bd （必看）

关于费马小定理：https://www.bilibili.com/video/BV1vt411Z7Yb （选看）

输入格式

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

输出格式

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

4
4 3
8 5
6 3
88888 1000000007

1
2
impossible
589787152

提示

计算1801郭程

这一题是学长们给你们的爱，与我无关(?) 

特此注明