思想

如果p是质数，那么可以利用费马小定理a^(p - 1) = a(mod p)得，其实逆元就死a^(p - 2)所以就可以使用快速幂来求解答案。

java 代码

import java.util.*;
class Main{
    static int n = 0;
    static long gcd(long a, long b){
        return b != 0 ? gcd(b, a % b) : a;
    }
    static long qmi(long a, long p, long b){
        long k = b;
        long res = 1;
        while(k != 0){
            if((k & 1) != 0)res = res * a % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while(n -- != 0){
            long a = sc.nextLong();
            long p = sc.nextLong();
            //存在最大公约数是1表示a p互质
            if(gcd(a, p) == 1)System.out.println(qmi(a, p, p - 2));
            else System.out.println("impossible");

        }
    }
}

扩展的欧几里得算法

证明请见：https://blog.csdn.net/zhjchengfeng5/article/details/7786595

import java.util.*;
class Main{
    static int n = 0;
    static long x = 0, y = 0;

    static long qmi(long a, long b){
        if(b == 0){
             x = 1; y = 0;
             return a;
        }
        long temp = x;
        x = y;
        y = x;
        long d = qmi(b, a % b);
        temp = x;
        x = y;
        y = temp - (a / b) * y;
        return d;
    }
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while(n -- != 0){
            long a = sc.nextLong();
            long b = sc.nextLong();
            //存在最大公约数是1表示a p互质
            long res = qmi(a, b);
            if(res == 1)System.out.println((x + b) % b);
            else System.out.println("impossible");
        }
    }
}