逆元杂烩

· · 个人记录

逆元，简单来说就是为了满足在取模式下的除法需要（+-*可在取模式下正常进行，除法不行） 同余式规则见同余入门

用数学式说 ax≡1(mod p) 则x为a在膜p意义下的逆元

求法：

1.欧拉定理法

根据欧拉定理a^£(p)≡1(mod p)

x=a^£(p)-1

所以就可以求欧拉函数+快速幂求逆元

条件gcd(a,p)=1

时间：o（sqrt(n)）

2.费马小定理

根据费马小定理a^(p-1)≡1(mod p)

x=a^(p-2)

所以快速幂直接解决

条件：p为质数

时间：o(log(p))

3.exgcd

ax≡1(mod p)

ax-py=1

用exgcd求其最小解即可

条件a，p互质

时间：o(log(a))

代码:

il void exgcd(int a,int b,ll &x,ll &y)
{
    if(!b) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}

4.线性递推求逆元

设p=ki+t≡0(mod p)

k+t*i^(-1)≡0(mod p)

t * i^(-1)≡-k(mod p)

i^(-1)≡-k*t^(-1) (mod p)

i^(-1)≡p-k*t^(-1) (mod p)

inv[i]≡p-(p/i)*inv[p%i] (mod p)

限制：无

时间：o(n) (一下求n个，且是线下算法）

代码：

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

5.阶乘法求逆元

对于一串数a1,a2,……,an 求每个数的逆元

首先维护数一个累积数组s，s[i]=a1a2……ai

然后，再求s[n]的逆元，记为inv[n+1]（inv数组表示1/（a1a2……ai-1））

最后，反向for一遍，ai的逆元为s（i-1)inv(i+1)（a1 a2……ai-1/(a1 a2……*ai）==1/ai)

限制：无

时间：o(n) (一下求n个，且是线下算法）

代码：

    s[0]=1;
    for(ri i=1;i<=n;i++)
    {
        a[i]=read();
        s[i]=(s[i-1]*a[i])%p;
    }
    inv[n+1]=ksm(s[n],p-2);
    for(ri i=n;i>=1;i--)
    {
        inv[i]=(inv[i+1]*a[i])%p;
    }
    for(ri i=1;i<=n;i++)
    {
        ny[i]=(inv[i+1]*s[i-1])%p;
    }

以上是常规求逆元方法，还有其他方法望各位挖掘