莫欺少年穷，修仙之旅在这开始—>算法基础课题解

快速幂求逆元

前提： $p$ 是质数，$a$ 与 $p$ 互质

证明：

$\because ax\equiv1\pmod{p},a^{p-1}\equiv1\pmod{p}$

$\therefore x\equiv{a^{p-2}}\pmod{p}$

#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;
        a=(LL)a*a%p;
        b>>=1;
    }

    return res;
}

int main()
{
    int n;
    cin>>n;

    while(n--)
    {
        int a,p;
        cin>>a>>p;

        if(a%p) cout<<qmi(a,p-2,p)<<endl;
        else cout<<"impossible"<<endl;
    }

    return 0;
}