乘法逆元

若**\(ax≡1 \pmod f\), 则称a（关于1）模f的乘法逆元为x。也可表示为\(ax≡1\pmod f\)**。

当a与f互素时，a关于模f的乘法逆元有解。如果**不互素，则无解**。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。

欧几里德算法

其求法可用**欧几里德算法**： exgcd算法求d关于模f的乘法逆元d-1 ，即 d* d-1 mod f = 1 它适用于所有情况下求解逆元！

伪代码

 (X1，X2，X3) := (1，0，f)； (Y1，Y2，Y3) := (0，1，d)
 if (Y3=0) then return d-1 = null //无逆元
 if (Y3=1) then return d-1 = Y2 //Y2为逆元
 Q := X3 div Y3 //整除
 (T1，T2，T3) := (X1 - QY1，X2 - QY2，X3 - Q*Y3)
 (X1，X2，X3) := (Y1，Y2，Y3)
 (Y1，Y2，Y3) := (T1，T2，T3)
 goto 2

代码

int x,p,a,n,y;
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;
}
signed main() {
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++){
        exgcd(i,p,x,y);
        x=(x%p+p)%p;
        printf("%d\n",x);
    }
    return 0;
}

费马小定理

求此算法还可以使用**费马小定理** 只不过局限性比较大，要求模数是素数 \(a^{p-1} =1\pmod p\) p要求是素数 那么\(a^{p-2}\)就是a的乘法逆元

线性递推

\(inv[i]=(p−⌊\frac{i}{p}​⌋×inv[p\%i]\%p)\%p\)

inv[1]=1;
for(int i=2;i<=n;i++){
    inv[i]=(p-p/i)*inv[p%i]%p;

分数取模

通常我们要输出分数时，题目会要求我们对分数进行取模后输出。此时我们将分数的分母变成逆元形式乘上分子即可。

不好维护分母和分子？对模数取模的分数还有一个很好的性质：

要把两个分数相加，就直接把两个分数（取模后）相加即可！相乘也是一样。