逆元：
对于a和p，若 a * inv(a) % p ≡ 1，则称inv(a)为a%p的逆元。其中p为质数
逆元就是在mod下，不能直接除以一个数，而要乘以他的逆元
a * inv(a) = 1 (mod p)
x / a可以改成 x * inv(a) % p
方法一.扩展欧几里得
a * inv(a) = 1 (mod p)
可以变形成 a * inv(a) +k * p = 1(前提是a和p要互素)
可以用扩欧的公式来计算
时间复杂度:O(logn)
适用范围：只要存在逆元即可求，适用于个数不多但是mod很大的时候，也是最常见的一种求逆元的方法。
代码：
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{
if(b==0)
{
x=1;
y=0;
return a; //到达递归边界开始向上一层返回
}
ll gcd=exgcd(b,a%b,x,y);
ll y1=y; //把x y变成上一层的
ll x1=x;
y=x1-(a/b)*y1;
x=y1;
return gcd; //得到a b的最大公因数
}
ll inv(ll a,ll mod){
ll x,y;
ll gcd=exgcd(a,mod,x,y);
if(gcd!=1)return -1;
else return (x+mod)%mod;
}
方法二.费马小定理+欧拉定理
费马小定理：假如p是质数，且gcd(a,p)=1，那么 a(p-1) ≡ 1（mod p），进一步可以推出ap-2 * a ≡ 1 (mod p)
ap-2就是a在mod p意义下的逆元
欧拉函数：aφ(n)≡1 (mod n) ，其中 gcd(a,n)=1
若n为素数，φ(n)=n-1
时间复杂度 O(log mod)
适用范围：在mod是素数的时候使用，比扩欧快
代码：
ll poww(ll a,ll b,ll mod){
ll ans=1;
ll base=a;
while(b){
if(b&1)ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans%mod;
}
ll inv(ll a,ll mod){
return poww(a,mod-2,mod);
}
方法三:递推求逆元
时间复杂度为O（n）
使用条件：mod为不是很大的素数，且需要多次调用
代码
long long inv[maxn];
void init(long long n,long long p)
{
inv[1]=1;
for(int i=2;i<=n;i++)
{
inv[i]=((p-p/i)*inv[p%i]%p);
}
}
京公网安备 11010502036488号