4-快速幂求乘法逆元

算法思想

算法模板

import java.util.*;
public class Main {
    static int N = 100010;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while(n -- > 0)
        {
            int a = sc.nextInt();
            int p = sc.nextInt();
            if(a % p == 0) System.out.println("impossible");
            // 根据费马小定理可得出下述公式
            else System.out.println(qmi(a, p - 2, p));
        }
    }
    
    public static int qmi(long a, int b, int p)
    {
        long res = 1;
        while(b > 0)
        {
            int l = b >> 0 & 1;
            if(l > 0) res = res * a % p;
            a = a * a % p;
            b >>= 1;
        }
        return (int)res;
    }
}

参考资料

1. G13 同余式 乘法逆元 费马小定理_哔哩哔哩_bilibili