好长时间没用到过逆元了
逆元是什么
我们都知道 (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^(-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