什么是逆元?
乘法逆元:
- 模p意义下,一个数a如果有逆元x,那么除以a相当于乘以x。
- 在模n的意义下,a存在逆元的充要条件是**n不等于1,且(a,n)互质。怎样求逆元?
- 费马小定理(有限制)
=》p为素数时,a关于mod p的逆元为a^(p-2)mod p。用快速幂模。 - 扩展欧几里得算法(普遍适用)
- 给定模数n,求a的逆元
- 即ax=1(mod n)
- =》ax-ny=1
- 所以可用扩展欧几里得, ax+by=gcd(a,b)求逆元,即求x的值。注意:存在逆元的判断条件是 a,m互质。
if(gcd(a,m) != 1) //a,m不互质,则不存在逆元
cout << "Not Exist" << endl;
else
{
ext_gcd(a, m, x, y);
LL ans = (x<=0) ? (x%m+m) : x; //有可能x是负数,x要先取模再加
cout << ans << endl;
0