所谓一个数 的逆元，就是一个 使

即

法一：快速幂(费马小定理)求逆元

由费马小定理得：

那么将就可以将拆成，得：

根据逆元的定义就是的逆元
然而就可以用快速幂来求
source:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod = 19;
long long quickpow(long long a, long long b) {
    if (b < 0) return 0;
    long long ret = 1;
    a %= mod;
    while(b) {
        if (b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a=(a*a) % mod;
    }
    return ret;
}
long long inv(long long a) {
    return quickpow(a, mod - 2);
}
int main(){
    long long a;
    scanf("%lld",&a);
    printf("%lld\n",inv(a));
    return 0;
}

法二：扩展欧几里得算法算法求逆元

根据上面对逆元的解释：
利用扩展欧几里得算法：
那么对于数的逆元就是用扩欧找到一个使
source:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
void extend_gcd(ll a, ll b, ll &x, ll &y) {
    if (!b)
    {
        x = 1, y = 0;
        return;
    }
    else
    {
        extend_gcd(b, a % b, y, x);
        y -= x * (a / b);
        return;
    }
}
ll inv(ll a, ll n) {
    ll x, y;
    extend_gcd(a,n,x,y);
    x = (x % n + n) % n;
    return x;
}
int main(){
    ll a,p;
    scanf("%lld%lld",&a,&p);
    printf("%lld\n",inv(a,p));
    return 0;
}

法三：线性求1~p-1的逆元

以下公式都应该是在模p意义下的
因为

即

挪一下再调个边

那么

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int inv[1000];
int main(){
    int p;
    cin>>p;
    inv[1]=1;
    for(int i=2;i<p;i++) inv[i]=inv[p%i]*(p-p/i)%p;
    for(int i=1;i<p;i++) printf("%d ",inv[i]);
    printf("\n");
}

，这数学公式用的好爽！
参考博客：boshi 基本是抄的