也就是a * b == 1(mod p), p为质数
求解a在模p下的逆元b

小费马定理:a^p-1 == 1(mod p), p为质数

a * a^p-2 == 1(mod p) b就为a^p-2

import java.util.*;

public class Main{

    static int a, k, p;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t-- > 0) {
            a = sc.nextInt();
            p = sc.nextInt();

            if (a % p == 0) {
                System.out.println("impossible");
                continue;
            }

            int res = quick_mi(a, p - 2, p);

            System.out.println(res);
        }
    }

    static int quick_mi(int a, int k, int p) {
        long res = 1;

        while (k != 0) {
            if ((k & 1) == 1) res = res * a % p;
            k >>= 1;
            a = (int) ((long) a * a % p);
        }
        return (int)res;
    }
}

exgcd求逆元(并没有要求模数为质数,根据d来判断是否有逆元)

a有逆元的条件为:gcd(a, p) = 1
a在模p下的逆元为b：a * b == 1(mod p)
a * b + p * y = 1
d = exgcd(a, p, b, y);
如果d==1, 有逆元b,将b换成正整数即可(b%p+p)%p
注意变量的名称即可

import java.util.Scanner;

public class Main {
    static long[] x = new long[1], y = new long[1];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            long a = sc.nextLong(), b = sc.nextLong(), m = sc.nextLong();

            long d = exgcd(a, m, x, y);
            if (d == 1) {
                System.out.println((x % m + m) % m);
            } else {
                System.out.println("impossible");
            }

        }
        sc.close();
    }

    static long exgcd(long a, long b, long[] x, long[] y) {
        if (b == 0) {
            x[0] = 1;
            y[0] = 0;
            return a;
        }
        long d = exgcd(b, a % b, y, x);
        y[0] -= a / b * x[0];
        return d;
    }
}