代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % p;
        b = b >> 1;
        a = (LL)a * a % p;
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    while(n--){
        int a, p;
        scanf("%d%d", &a, &p);
        int t =  qmi(a, p-2, p);
        if(a % p) printf("%d\n", t);
        else puts("impossible"); 

    }
    return 0;
}

核心

快速幂