①公式法

公式： $\frac{1}{a}\%p=\frac{1\%\left(ap\right)}{a}$a1​%p=a1%(ap)​
举个例子： $\frac{8}{4}\%7=\frac{8\%(4\ast 7)}{4}=\frac{8}{4}=2$48​%7=48%(4∗7)​=48​=2
但是这个公式不能求那种本来就是分数的比如 $\frac{1}{4}\%7$41​%7
这种就要用到其他方法

②扩展欧几里得求逆元

扩展欧几里得是解决这种问题的：
$ax+by=gcd(a,b)$ax+by=gcd(a,b)
互质的话 $gcd=1$gcd=1
那么 $ax+by=1$ax+by=1
这个式子相当于
$ax\%b=1$ax%b=1
也就是 $ax\equiv 1\left(modb\right)$ax≡1(mod b)
就变成
$x\equiv \frac{1}{a}\left(modb\right)$x≡a1​(mod b)
那么 $a$a的逆元也就是 $x$x啦

#include"iostream"
using namespace std;
const int MOD=1e9+7;
int x,y;
int exgcd(int a, int b, int &x, int &y,int c)
{
    if (b == 0)
    {
        x = c;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y,c);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}
int main()
{
    int N;
    while(cin>>N)
    {
        exgcd(N,MOD,x,y,1);
        cout<<((x%MOD)+MOD)%MOD<<endl;
    }
}

③逆元线性筛

假设要求 $1到p-1$1到p−1 所有的逆元，阔以用线性筛
$p=ki+r$p=ki+r
$ki+r\equiv 0\left(modp\right)$ki+r≡0 (mod p)
同时除一个 $ir$ir
$\frac{k}{r}+\frac{1}{i}=0\left(modp\right)$rk​+i1​=0 (mod p)
所以
$\frac{1}{i}\equiv -k\frac{1}{r}\left(modp\right)$i1​≡−kr1​ (mod p)
而
$k=p/i$k=p/i
$r=p\%i$r=p%i
所以
$\frac{1}{i}\equiv (-p/i)\left(p\%i\right)\left(modp\right)$i1​≡(−p/i)(p%i)     (mod p)
这样求出来可能是负的，直接加上 $p\%i个p$p%i个p 把他变成正的
完整的就是：

$\frac{1}{i}\equiv (p-p/i)\left(p\%i\right)\left(modp\right)$i1​≡(p−p/i)(p%i)     (mod p)

#include"bits/stdc++.h"
using namespace std;
const int maxn=5e4+5;
const int MOD=1e9+7;
long long inv[maxn];
int main()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<=10000;i++)
    {
        inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;
    }
    int N;
    while(cin>>N)
    {
        cout<<inv[N]<<endl;
    }
}

④费马小定理求逆元

如果能找到某个式子在模意义下等于1，那么变一下形就能找到他的逆元了，费马小定理就是这样
$a^{p-1}\equiv 1\left(modp\right)$ap−1≡1 (mod p)
$a\cdot a^{p-2}\equiv 1\left(modp\right)$a⋅ap−2≡1 (mod p)
$\frac{1}{a}\equiv a^{p-2}\left(modp\right)$a1​≡ap−2 (mod p)
所以逆元直接就是 $a^{p-2}$ap−2，直接用快速幂算出来就行了

⑤单次快速求逆元，没看懂

LL inv(int x)
{
  LL r = 1;
  for (; x > 1; x = MOD % x)
    r = r * LL(-MOD/x) % MOD;
  return (r+MOD)%MOD;
}