逆元

逆元素是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。

在要取模大整数的除法中，我们常常会遇到这样一个问题：

$6\mod 5=1$

$ 3\mod 5=3$

但$(6\div 3 )\mod5=2$

$(1\div3)\mod5=???$

由此可见除法取模运算不能再套用和的模的等于膜的和的模，或是积的模等于模的积的模来算了。
我们知道在除以一个数就是乘以它的倒数，倒数是数学广义定义的逆元，如果我们要对要两个作商的数取模，我们是不是也可以找一个不是分数而和倒数具有相同作用的数呢？这样我们就可以用之前积的模等于模的积的模这个结论算出答案。

exgcd

我们首先把这个问题用数学方法表示出来

\[x\equiv a^{-1}(mod p) \]

其中$a^{-1}$是逆元，而我们只要找到一个最小的正整数x，就可以得到逆元了。
补充一个知识：
在同余方程里，满足：如果$gcd(a,p)=1$则 $x\equiv ay(mod p)$等价于$ax\equiv ay(mod p)$
把之前的式子化一下就可以得到：

\[ax\equiv 1(mod p) \]

现在就变成了一个解同余方程的问题了。
考虑把右边写成写成$-kp+1$的形式，把k和p的名字换成y和b，那么可以转化问题为求不定方程$$ax+by=1$$的解。
我们知道如果a，b互质那么$gcd(a,b)=gcd(b,a\% b)=1$。设$a_1=b,b_1=a\%b,$那么同样对于这一组$a_1,b_1$也可以求解他们对应的$x_1,y_1$,接下来找$x_1,y_1$和$x,y$之间的联系。
仿照上面的形式。可以很容易地写出方程。

\[a_1x_1+b_1y_1=1 \]

即$$bx_1+(a-(a/b)*b)y_1=1$$
展开，提出含a含b的项，合并同类项：

\[ay_1+b(x_1-a/b*y_1)=1 \]

\[ax+by=1 \]

对比发现$x=y_1,y=(x_1-(a/b)*y_1)$。
一步一步递归求解，到$a_n=1,b_n=0$的时候$x_n$显然就等于1,$y_n$显然为0。
代码很简单：

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

逆元的线性求法

显然 $e[1]=1$;
然后设$p=ki+r,k=\lfloor a/b\rfloor,r=p%i $. 那么$$p\equiv0(mod p)$$

\[ki+r\equiv0(mod p) \]

同乘$i^{-1}r^{-1}$

\[k*r^{-1}+i^{-1}\equiv 0 (modp) \]

整理得：

\[i^{-1}\equiv-(p/i)*e[p\%i] \]

代码

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

逆元

exgcd

逆元的线性求法

推荐阅读