乘法逆元

一、逆元的定义

若 $a \cdot x \equiv 1 \ (\bmod \ p)$ 且 $(a,p)=1$ ，则称 $a$ 关于模 $p$ 的乘法逆元为 $x$ ，记为 $a^{-1}$ 。

二、逆元的求法

1.费马（Fermat）小定理

若 $p$ 为素数，且 $(a,p)=1$ ，则有 $a^{p-1} \equiv 1 \ (\bmod \ p)$ 。

由费马小定理 $$a \cdot a^{p-2} \equiv 1 \ (\bmod \ p)$$ 则 $a^{p-2}$ 即为 $a$ 的逆元。

inline int Pow(int x,int y,int p){
    int res=1;
    for(;y;y>>=1){
        if(y&1)
            (res*=x)%=p;
        (x*=x)%=p;
    }
    return res;
}
inline void inv(int x,int p){
    return Pow(x,p-2,p);
}

2.欧拉（Euler）定理

若 $(a,m)=1$ ，则 $a^{\varphi(m)} \equiv 1 \ (\bmod \ m)$ 。

当不满足 $p$ 为素数时，可用欧拉定理解决。
与费马小定理类似，此时 $a$ 的逆元为 $a^{\varphi(p)-1}$ 。

3.扩展欧几里得（Euclid）算法

将 $$a \cdot x \equiv 1 \ (\bmod \ p)$$ 变形为 $$ax+py=1$$ 其中 $y \in \mathbb{Z}$ 。此方程可由扩展欧几里得算法解出，解出的 $x$ 即为 $a$ 的逆元，解出的 $y$ 为辅助解。

void exgcd(int a,int b,int& x,int& y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    int t=x;
    x=y;
    y=t-x/y*y;
}
inline int inv(int x,int p){
    int x0,y0;
    exgcd(x,p,x0,y0);
    return x0;
}