逆元： 对于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
;
ll x1
=x
;
y
=x1
-(a
/b
)*y1
;
x
=y1
;
return gcd
;
}
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
);
}
}
