乘法逆元

定义

​

​

这里x就是a的逆元。

一个数有逆元的充分必要条件是gcd(a,p)=1，此时逆元唯一存在。

求解逆元的方式

拓展欧几里

若m不为质数，可以使用拓展欧几里得求逆元

根据裴蜀定理，若gcd(a,b)=1则gcd是a,b两个数线性组合的最小值，其他组合都是gcd的倍数。

​

​

gcd(a,b)=1，满足

移项得

即ax≡1 mod ，此时的x就是逆元。实际上线性不定方程组有无穷多解，这里只求正的最小逆元。

推导过程

​

​

扩欧代码

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;x=y;y=z-y*(a/b);
    return d;
}

ans=(x%b+b)%b;//x可能是负数，需要处理

费马小定理

若模数p为质数，还可以根据费马小定理求逆元

​

，此时逆元x可取为

。

线性求逆元

模数p为质数，可在线性时间推出1∼n的所有逆元。

​

证明

​

​

​

由上可得出 dp[i]=(p-p/i)*dp[p%i]

常见用途

将对结果取余的较大数字的除法，转成乘法进行计算。

​

Q.E.D.