逆元的求法

逆元

逆元(Inverse element)是群论中的一个概念，大致意思是指能消除另一种运算影响的元素，例如在实数的乘法运算中，乘x的逆元就是乘$\frac{1}{x}$。算法类一般需要求的是对于取模运算的除法逆元。

假设$a*b\equiv1\space mod \space p$,即a与b在$mod \space p$的意义下互为逆元，那么如果我们要求$x/a\space mod \space p$就可以转化为$x*b\space mod \space p$，求逆元必须满足$a$与$p$是互质的，否则不存在逆元

逆元的求法

1.拓展欧几里得求逆元

原理
$a*b\space\equiv\space 1(mod\space p)$可转化为$a*b+k*p=1$
则我们可以利用拓展欧几里得对于已知的互质两数$a$与$p$求的一组$b$与$k$

代码

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法 
{
	if(b==0)
	{
        x=1,y=0;
		return a;
    }
  	ll ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
ll getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1 
{
    ll x,y;
    ll d=exgcd(a,mod,x,y);
    return d==1?(x%mod+mod)%mod:-1;
}

时间复杂度：$O(logn)$
适用范围：只要存在逆元即可求，适用于个数不多但是mod很大的时候，也是最常见的一种求逆元的方法。

2.费马小定理/欧拉定理

原理
费马小定理：若p为素数，则有$a^{p-1}\equiv\space 1(mod\space p)$
所以可以推得$a*a^{p-2}\space\equiv\space 1(mod \space p)$
即$a^{p-2}$是$a$的逆元
欧拉定理:若$a$、$p$互质，则有$a^{\varphi (p)}\equiv 1 \space (mod \space p)$ 『$\varphi (p)$是$p$的欧拉函数值』
所以$a^{\varphi (p)-1}*a\equiv 1 \space (mod \space p)$
即$a^{\varphi (p)-1}$是$a$的逆元
费马小定律其实就是p为质数时的情况

代码

ll qkpow(ll a,ll p,ll mod)
{
    ll t=1,tt=a%mod;
    while(p)
    {
        if(p&1)t=t*tt%mod;
        tt=tt*tt%mod;
        p>>=1;
    } 
    return t;
}
ll getInv(ll a,ll mod)
{
    return qkpow(a,mod-2,mod);
}

时间复杂度：$O(logmod)$
适用范围：一般mod为素数时使用，比扩欧更快而且好写，但如果是合数则需要额外计算欧拉函数值

3.线性递推求逆元

原理
设$p$为模数，i为待求的逆元，我们求的是$i^{-1}$在$mod \space p$意义下的值
$p=k*i+r 令r<i,则k=p/i，r=p%i$
$k*i+r \equiv\space 0(mod\space p)$
$k*r^{-1}+i^{-1}\equiv 0(mod\space p)$
$i^{-1}\equiv -k*r^{-1}(mod\space p)$
$i^{-1}\equiv -p/i*inv[p\space mod \space i] $
没看太懂能用就行

代码

线性求逆元

//调用前需要预处理inv数组并先对除数模mod
ll inv[mod+5];
void getInv(ll mod)
{
    	inv[1]=1;
    	for(int i=2;i<mod;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

+  时间复杂度：$O(n)$
+  适用范围：mod数是不大的素数而且多次调用

递归求逆元

ll inv(ll i)
{
	if(i==1)return 1;
	return (mod-mod/i)*inv(mod%i)%mod;
}

+  时间复杂度：$O(logmod)$
+  适用范围：mod数是素数