快速幂
乘法逆元
乘法逆元的定义 若整数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的乘法逆元。
AcWing 875. 快速幂 原题链接
给定nn组ai,bi,piai,bi,pi，对于每组数据，求出abii mod piaibi mod pi的值。
输入格式
第一行包含整数nn。
接下来nn行，每行包含三个整数ai,bi,piai,bi,pi。
输出格式
对于每组数据，输出一个结果，表示abii mod piaibi mod pi的值。
每个结果占一行。
数据范围
1≤n≤1000001≤n≤100000, 1≤ai,bi,pi≤2∗1091≤ai,bi,pi≤2∗109
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
private static int fastPower(long a, long b, long q) {
long res = 1L;
while (b > 0) {
if ((b & 1) == 1) {
res = res * a % q;
}
b >>= 1;
a = a * a % q;
}
return (int) res;
}
AcWing 876. 快速幂求逆元 原题链接
给定nn组ai,piai,pi，其中pipi是质数,求aiai模pipi的乘法逆元，若逆元不存在则输出impossible。
注意：请返回在0∼p−10∼p−1之间的逆元。
乘法逆元的定义
若整数b，mb，m互质，并且对于任意的整数 aa，如果满足b|ab|a，则存在一个整数xx，使得a/b≡a∗x(mod m)a/b≡a∗x(mod m)，则称xx为bb的模mm乘法逆元，记为b−1(mod m)b−1(mod m)。 bb存在乘法逆元的充要条件是bb与模数mm互质。当模数mm为质数时，bm−2bm−2即为b的乘法逆元。
输入格式
第一行包含整数nn。
接下来nn行，每行包含一个数组ai,piai,pi，数据保证pipi是质数。
输出格式
输出共nn行，每组数据输出一个结果，每个结果占一行。
若aiai模pipi的乘法逆元存在，则输出一个整数，表示逆元，否则输出impossible。
数据范围
1≤n≤1051≤n≤105, 1≤ai,pi≤2∗1091≤ai,pi≤2∗109
输入样例：
3
4 3
8 5
6 3
输出样例：
1
2
impossible
private static int fastPower(long a, long b, long q) {
long res = 1L;
while (b > 0) {
if ((b & 1) == 1) {
res = res * a % q;
}
b >>= 1;
a = a * a % q;
}
return (int) res;
}
public static void main(String[] args) {
int n = in.nextInt();
while (n-- > 0) {
int a = in.nextInt();
int b = in.nextInt();
if (a % b == 0) {
out.println("impossible");
}else {
out.println(fastPower(a, b - 2, b));
}
}
out.flush();
out.close();
}