快速幂
点它

int qmi(int a,int k,int p)  // 求a^k mod p
{
    int res=1;
    while(k)
    {
        if(k&1) 
            res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}

快速乘

int fast_multiply(int a,int b,int mod)
{
    int ans=0;
    while(b!=0)
    {
        if(b%2==1)//或写成b&1
        {
            ans+=a;
            ans%=mod;
        }
        a+=a;
        a%=mod;
        b/=2;//或写成b>>=1;
    }
    return ans;
}

快速幂求逆元
本人太菜数论学不会
转载分析证明费马定理结合

#include <iostream>
#include <cstring>
#include <algorithm>


using namespace std;

typedef long long LL;

int qmi(int a,int k,int p)  // 求a^k mod p
{
    int res=1;
    while(k)
    {
        if(k&1) 
            res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}



int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,k,p;
        scanf("%d %d",&a,&p);
        int res=qmi(a,p-2,p);
        if(a%p!=0)
            printf("%d\n",res);
        else printf("impossible\n");

    }
    return 0;
}