逆元合集

好长时间没用到过逆元了

逆元是什么

我们都知道 (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) ，且a与p互质，那么我们就能定义: x 为 $a$ 的逆元，记为a^(-1)

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

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

一、快速幂求逆元

这里要用到费马小定理：若p为素数，a为正整数，且a，p互质。则有$a^(p-1)\; \equiv \; 1\; (mod\; 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