逆元合集

好长时间没用到过逆元了

逆元是什么

我们都知道 (a*b)%p = ((a%p) * (b%p))%p

那 (a/b)%p 怎么算呢

首先(a/b)%p != ( (a%p) / (b%p) )%p

除以一个数再取模等于乘以这个数的逆元再取模

假设b的逆元为inv[b],那么(a/b)%p = ( a*inv[b] )%p

我们不能说一个数的逆元是多少,要说一个数在模 P 意义下的逆元为多少

定义:若 a * x ≡ 1 (mod p) ,ap互质,那么我们就能定义: x 为  的逆元,记为a^(-1)

那么 a 在模p的意义下有没有逆元呢

a 关于 p 的逆元存在,当且仅当 a 和 p 互质,即 gcd(a,p)=1

 

一、快速幂求逆元

这里要用到费马小定理:若p为素数,a为正整数,且a,p互质。则有

a^(p-1) % p=1

a * x % p =1

x = a ^(p-2) (mod p)

所以a ^(p-2) (mod p)就是 a 的逆元了

举个例子:

求组合数C(n,k) % p

C(n,k) = n! / ( k! * (n-k)! )

C(n,k) = n! * ( k! *(n-k)! )^ (p-2)   %p

代码:

ll C(ll n,ll k)
{
    //求n的阶乘
    ll aa=1;
    for(ll i=1;i<=n;i++)
    {aa=aa*i%p;}
    aa%=p;
    //求m的阶乘
    ll bb=1;
    for(ll i=1;i<=k;i++)
    {bb=bb*i%p;}
    //求n-k的阶乘
    for(ll i=1;i<=n-k;i++)
    {bb=bb*i%p;}
    bb%=p;
    return aa*apow(bb,p-2)%p; //apow为快速幂函数(在这就不写了)
}

二、扩展欧几里得求逆元

利用扩展欧几里得求线性同余方程 a * x ≡ c (mod p) 在c=1 的情况下的一个解

而且这个求法需要p为质数,只要保证a、p互质就行了

首先来看一下同余方程 a ≡ b (mod p)

a ≡ b (mod p) 成立的充要条件为 a-b 是 p 的整数倍

那么就可以得到这样一个式子

a * x ≡ 1 (mod p)  ⇒   a * x - 1 =  y * p   ⇒  a * x + y * p = 1

扩展欧几里得算法就是求解a * x + y * b = 1 的一个最小整数解(x为逆元)

注意最后算出的x可能为负数,要想得到正数的话可以 (x+p) % p

模板代码:

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

三、线性求逆元

用于求一连串数字对于一个(mod p)的逆元

首先由一个:1^(-1) ≡ 1 (mod p)

然后设 p = k * i + r ,(1<r<i<p) k是 p/i 的商 ,r 是余数

再将这个式子放到(mod p)意义下就会得到:

                   k * i + r ≡ 0 (mod p)

然后乘上i^(-1) 、r^(-1) 就可以得到:

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

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

i^(-1) ≡ -( p / i ) * ( p % i )^(-1) (mod p)

代码:

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

四、阶乘求逆元

直接写结论吧,懒的推导了(其实是不会)

inv[i] ≡ inv[i+1] *(i+1) (mod p)

123

参考文章:1、https://blog.csdn.net/qq_35416331/article/details/81059747

2、https://www.luogu.com.cn/problemnew/solution/P3811

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注