算法基础课的笔记：

扩展欧几里得算法求逆元

对于求a * x ≡ 1 (mod p)中的乘法逆元,即求x,由欧几里得算法可以得出，原式中的x等价于
式 a * x + p * y = 1中的x
所以我们可以利用扩展欧几里得算法来求乘法逆元

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

int n,p;

void exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
    }
    else
    {
        exgcd(b,a%b,y,x);
        y -= a/b*x;
    }
}

int main()
{
    cin>>n;

    while(n --)
    {
        int a,p,x,y;

        scanf("%d%d",&a,&p);
        exgcd(a,p,x,y);

        if(x)
            printf("%d\n",((LL)x+p)%p); //x可能为负数
        else
            puts("impossible");
    }

    return 0;

}

快速幂求逆元：

算法基础课y总给出的大致证明

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;

int n,p;

LL qmi(int a,int k,int p)
{
    LL res = 1;
    while(k)
    {
        if(k&1) res = (LL)res*a%p;
        a = a*(LL)a%p;
        k>>=1;
    }
    return res;
}
int main()
{
    cin>>n;

    while(n--)
    {
        int a,p;
        scanf("%d%d",&a,&p);
        if(a%p)
            printf("%d\n",qmi(a,p-2,p));
        else
            puts("impossible");
    }

    return 0;
}

递推法：

对于输出一系列的mod p的逆元，我们可以使用递推法

(递推公式 : inv[b] = (p-p/b) * inv[ p % b ] % p)

inv[1] = 1;
for(int i = 2; i<=n ;i++)
{
    inv[i] = (LL)(p-p/i)*inv[p%i]%p;
    printf("%d\n",inv[i]);
}